Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
420003 | Discrete Applied Mathematics | 2013 | 8 Pages |
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
Rija Erveš, Janez Žerovnik,