Record number :
1599376
Title of article :
Wide diameter of Cartesian graph bundles
Author/Authors :
Bani?، نويسنده , , Iztok and ?erovnik، نويسنده , , Janez، نويسنده ,
Issue Information :
روزنامه با شماره پیاپی سال 2010
Pages :
5
From page :
1697
To page :
1701
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 D c ( G ) the c -diameter of G and κ ( 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 ≤ κ ( F ) , and 0 < b ≤ κ ( B ) . We prove that D a + b ( G ) ≤ D a ( F ) + D b ( B ) + 1 . Moreover, if G is a graph bundle with fiber F ≠ K 2 over base B ≠ K 2 , then D a + b ( G ) ≤ D a ( F ) + D b ( B ) . The bounds are tight.
Keywords :
Cartesian graph products , Cartesian graph bundles , Wide diameter
Journal title :
Discrete Mathematics
Serial Year :
2010
Link To Document :
بازگشت