×

Fault diameter of product graphs. (English) Zbl 1185.05054

Summary: 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 \(D_{k_{1}+k_{2}}(G_{1}*G_{2}) \leqslant 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 Banič and Žerovnik [I. Banič and J. Žerovnik, “Fault-diameter of Cartesian graph bundles”, Inf. Process. Lett. 100, No.2, 47–51 (2006; Zbl 1185.05121)].

MSC:

05C12 Distance in graphs
05C40 Connectivity
05C76 Graph operations (line graphs, products, etc.)
68R10 Graph theory (including graph drawing) in computer science

Citations:

Zbl 1185.05121
Full Text: DOI

References:

[1] Balbuena, C.; García-Vázquez, P.; Marcote, X., Reliability of interconnection networks modelled by a product of graphs, Networks, 48, 3, 114-120 (2006) · Zbl 1108.05053
[2] Banič, I.; Žerovnik, J., Fault-diameter of Cartesian graph bundles, Inform. Process. Lett., 100, 2, 47-51 (2006) · Zbl 1185.05121
[3] Bermond, J. C.; Delorme, C.; Farhi, G., Large graphs with given degree and diameter II, J. Combin. Theory, Ser. B, 36, 32-48 (1984) · Zbl 0539.05038
[4] Chartrand, G.; Harary, F., Planar permutation graphs, Ann. Inst. H. Poincaré, Sec. B, 3, 433-438 (1967) · Zbl 0162.27605
[5] Krishnamoorthy, M. S.; Krishnamurthy, B., Fault diameter of interconnection networks, Comput. Math. Appl., 13, 5-6, 577-582 (1987) · Zbl 0641.94048
[6] Pisanski, T.; Shawe-Taylor, J.; Vrabec, J., Edge-colorability of graph bundles, J. Combin. Theory, Ser. B, 35, 12-19 (1983) · Zbl 0505.05034
[7] Xu, J.-M., Topological Structure and Analysis of Interconnection Networks (2001), Kluwer Academic Publishers: Kluwer Academic Publishers Dordrecht/Boston/London · Zbl 1046.68026
[8] Xu, J.-M., Theory and Application of Graphs (2003), Kluwer Academic Publishers: Kluwer Academic Publishers Dordrecht/Boston/London · Zbl 1035.05003
[9] Xu, M.; Xu, J.-M.; Hou, X.-M., Fault diameter of Cartesian product graphs, Inform. Process. Lett., 93, 245-248 (2005) · Zbl 1169.05319
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.