Wide diameter of Cartesian graph bundles

Iztok Banič (Avtor), Janez Žerovnik (Avtor)

Povzetek

Fault tolerance and transmission delay of networks are important concepts in network design. The notions are strongly related to connectivity and diameter of a graph, and have been studied by many authors. Wide diameter of a graph combines studying connectivity with the diameter of a graph. Diameter with width ▫$k$▫ of a graph ▫$G$▫, ▫$k$▫-diameter, is defined as the minimum integer ▫$d$▫ for which there exist at least ▫$k$▫ internally disjoint paths of length at most ▫$d$▫ between any two distinct vertices in ▫$G$▫. Denote by ▫${\mathscr D}_c(G)$▫ the ▫$c$▫-diameter of ▫$G$▫ and ▫$\kappa(G)$▫ the connectivity of ▫$G$▫. In the context of computer networks, wide diameters of Cartesian graph products have been recently studied by many authors. Cartesian graph bundles is a class of graphs that is a generalization of the Cartesian graph products. Let ▫$G$▫ be a Cartesian graph bundle with fiber ▫$F$▫ over base ▫$B$▫, ▫$0 < a \le \kappa(F)$▫, and ▫$0 < b \le \kappa(B)$▫. We prove that ▫${\mathscr D}_{a+b}(G) \le {\mathscr D}_a(F) + {\mathscr D}_b(B) + 1$▫. Moreover, if ▫$G$▫ is a graph bundle with fiber ▫$F \ne K_2$▫ over base ▫$B \ne K_2$▫, then ▫${\mathscr D}_{a+b}(G) \le {\mathscr D}_a(F) + {\mathscr D}_b(B)$▫. The bounds are tight.

Ključne besede

matematika;teorija grafov;kartezični grafovski produkti;kartezični grafovski svežnji;ne zaključna dela;mathematics;graph theory;Cartesian graph products;Cartesian graph bundles;wide diameter;

Podatki

Jezik:	Angleški jezik
Leto izida:	2010
Tipologija:	1.08 - Objavljeni znanstveni prispevek na konferenci
Organizacija:	UL FS - Fakulteta za strojništvo
UDK:	519.17
COBISS:	17543176
ISSN:	0012-365X
Št. ogledov:	1870
Št. prenosov:	90
Ocena:	0 (0 glasov)
Metapodatki:

Ostali podatki

Sekundarni jezik:	Slovenski jezik
Sekundarne ključne besede:	Matematika;Teorija grafov;
URN:	URN:SI:UM:
Vrsta dela (COBISS):	Članek v reviji
Strani:	Str. 1697-1701
DOI:	10.1016/j.disc.2009.11.024
ID:	8723839