Wide diameter of Cartesian graph bundles

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

Abstract

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.

Keywords

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;

Data

Language:	English
Year of publishing:	2010
Typology:	1.08 - Published Scientific Conference Contribution
Organization:	UL FS - Faculty of Mechanical Engineering
UDC:	519.17
COBISS:	17543176
ISSN:	0012-365X
Views:	1870
Downloads:	90
Average score:	0 (0 votes)
Metadata:

Other data

Secondary language:	Slovenian
Secondary keywords:	Matematika;Teorija grafov;
URN:	URN:SI:UM:
Type (COBISS):	Article
Pages:	Str. 1697-1701
DOI:	10.1016/j.disc.2009.11.024
ID:	8723839