Mixed fault diameter of Cartesian graph bundles II

Rija Erveš, Janez Žerovnik


The mixed fault diameter D(p, q)(G) is the maximum diameter among all subgraphs obtained from graph G by deleting p vertices and q edges. A graph is (p, q)+connected if it remains connected after removal of any p vertices and any q edges. LetF be a connected graph with the diameter D(F) > 1, and B be (p, q)+connected graph. Upper bounds for the mixed fault diameter of Cartesian graph bundle G with fibre F over the base graph B are given. We prove that if q > 0, then D(p + 1, q)(G) ≤ D(F) + D(p, q)(B), and if q = 0 and p > 0, then D(p + 1, 0)(G) ≤ D(F) + max{D(p, 0)(B), D(p − 1, 1)(B)}.


Mixed fault diameter, Cartesian graph bundle, interconnection network, fault tolerance.

Full Text:


DOI: https://doi.org/10.26493/1855-3974.390.1c5

ISSN: 1855-3974

Issues from Vol 6, No 1 onward are partially supported by the Slovenian Research Agency from the Call for co-financing of scientific periodical publications