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 :