Abstract
Let G be a (k+1) -connected or (k+1) -edge-connected graph, where k∈N. 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 approximately n/k+2 if G is also triangle-free. If G does not contain 4-cycles then this bound can be improved further to approximately 5n/(k-1). 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 2n-1/3 if k = 2, and by approximately 3/k+2 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.
Original language | English |
---|---|
Pages (from-to) | 132-140 |
Number of pages | 9 |
Journal | Networks |
Volume | 70 |
Issue number | 2 |
DOIs | |
Publication status | Published - Sept 2017 |
Keywords
- diameter
- diameter-vulnerability
- edge-fault-diameter
- edge-fault-tolerant diameter
- fault-diameter
- fault-tolerant diameter
ASJC Scopus subject areas
- Information Systems
- Computer Networks and Communications