Improved upper bounds for vertex and edge fault diameters of Cartesian graph bundles

2012/12/19 by Janez Žerovnik, Žerovnik, Janez, Rija Erveš +1
Biochemistry, Genetics and Molecular Biology · Computer Science · Mathematics · Medicine · #Autophagy in Disease and Therapy #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #Endoplasmic Reticulum Stress and Disease #FOS: Computer and information sciences #FOS: Mathematics #Interconnection Networks and Systems #Ubiquitin and proteasome pathways #cs.DM #math.CO

paper · pdf · doi:10.48550/arxiv.1212.4670

arXiv admin note: substantial text overlap with arXiv:1002.2508

arxiv created 2012/12/19 · openalex publication_date 2012/12/19 · arxiv updated 2012/12/20 · openalex created_date 2022/10/05 · openalex updated_date 2026/07/28

Abstract

Mixed fault diameter of a graph G, \D_(a,b)(G), is the maximal diameter of G after deletion of any a vertices and any b edges. Special cases are the (vertex) fault diameter \D^V_a = \D_(a,0) and the edge fault diameter \D^E_a = \D_(0,a). Let G be a Cartesian graph bundle with fibre F over the base graph B. We show that (1) \D^V_a+b+1(G)≤ \D^V_a(F)+\D^V_b(B) when the graphs F and B are k_F-connected and k_B-connected, 0< a < k_F, 0< b < k_B, and provided that \D_(a-1,1)(F)≤ \D^V_a (F) and \D_(b-1,1)(B)≤ \D^V_b (B) and (2) \D^E_a+b+1(G)≤ \D^E_a(F)+\D^E_b(B) when the graphs F and B are k_F-edge connected and k_B-edge connected, 0≤ a < k_F, 0≤ b < k_B, and provided that \D^E_a(F)≥ 2 and \D^E_b(B)≥ 2.

Citations

• Mixed connectivity of Cartesian graph products and bundles

Related

• Improved bound on the number of edges of diameter-k-critical graphs
• Oriented Diameter of Mixed Graphs with Given Maximum Undirected Degree
• The Steiner diameter of a graph
• Approximating the diameter of a graph
• Diameter critical graphs