Premium
Bounds on the fault‐diameter of graphs
Author(s) -
Dankelmann Peter
Publication year - 2017
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.21758
Subject(s) - combinatorics , mathematics , bounded function , upper and lower bounds , enhanced data rates for gsm evolution , order (exchange) , graph , fault (geology) , discrete mathematics , computer science , telecommunications , mathematical analysis , finance , seismology , economics , geology
Let G be a ( k + 1 ) ‐connected or ( k + 1 ) ‐edge‐connected graph, where k ∈ ℕ . The k ‐fault‐diameter and k ‐edge‐fault‐diameter of G is the largest diameter of the subgraphs obtained from G by removing up to k vertices and edges, respectively. In this paper we give upper bounds on the k ‐fault‐diameter and k ‐edge‐fault‐diameter of graphs in terms of order. We show that the k ‐fault‐diameter of a ( k + 1 ) ‐connected graph G of order n is bounded from above by n − k + 1 , and by approximately4 k + 2 n if G is also triangle‐free. If G does not contain 4‐cycles then this bound can be improved further to approximately5 n( k − 1 ) 2. We further show that the k ‐edge‐fault‐diameter of a ( k + 1 ) ‐edge‐connected graph of order n is bounded by n – 1 if k = 1, by⌊2 n − 1 3⌋if k = 2, and by approximately3 k + 2 n if k ≥ 3 , and give improved bounds for triangle‐free graphs. Some of the latter bounds strengthen, in some sense, bounds by Erdös, Pach, Pollack, and Tuza (J Combin Theory B 47 (1989) 73–79) on the diameter. All bounds presented are sharp or at least close to being optimal. © 2017 Wiley Periodicals, Inc. NETWORKS, Vol. 70(2), 132–140 2017