Article ID Journal Published Year Pages File Type
420003 Discrete Applied Mathematics 2013 8 Pages PDF
Abstract

The mixed fault diameter D(p,q)(G)D(p,q)(G) is the maximum diameter among all subgraphs obtained from graph GG by deleting pp vertices and qq edges. A graph is (p,q)(p,q)+connected if it remains connected after the removal of any pp vertices and any qq edges. Let FF be a (p,q)(p,q)+connected graph and B≠K2B≠K2 be a connected graph. Upper bounds for the mixed fault diameter of the Cartesian graph bundle GG with fibre FF are given. We prove that if q>0q>0, then D(p+1,q)(G)≤D(p,q)(F)+D(B)D(p+1,q)(G)≤D(p,q)(F)+D(B), where D(B)D(B) denotes the diameter of BB. If q=0q=0 and p>0p>0, then D(p+1,0)(G)≤max{D(p,0)(F),D(p−1,1)(F)}+D(B)D(p+1,0)(G)≤max{D(p,0)(F),D(p−1,1)(F)}+D(B). In the case when p=q=0p=q=0, the fault diameter is determined exactly.

Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
, ,