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 |
Keywords:
combinatorics; diameter; fault diameter; product graphs; Cartesian graphs; Cartesian graph bundles; permutation graphsCitations:
Zbl 1185.05121References:
[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.