Fault diameter of product graphs

作者：Xu Jun Ming^*; Yang Chao

来源：Information Processing Letters, 2007, 102(6): 226-228.

DOI：10.1016/j.ipl.2007.01.011

• combinatorics
• diameter
• fault diameter
• product graphs
• Cartesian graphs
• Cartesian graph bundles
• permutation graphs

The (k - 1)-fault diameter D-k (G) of a k-connected graph G is the maximum diameter of an induced subgraph by deleting at most k - 1 vertices from G. This paper considers the fault diameter of the product graph G(1) * G(2) of two graphs G(1) and G(2) and proves that Dk1+k2(G(1) * G(2)) <= D-k1 (G(1)) + D-k2(G(2)) + 1 if G(1) is k(1)-connected and G(2) is k(2)-connected. This generalizes some known results such as Banic and Zerovnik [I. Banic, J. Zerovnik, Fault-diameter of Cartesian graph bundles, Inform. Process. Lett. 100 (2) (2006) 47-51].

• 出版日期2007-6-15
• 单位中国科学技术大学