Bounds on the fault-diameter of graphs

Research output: Contribution to journalArticlepeer-review

4 Citations (Scopus)

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 languageEnglish
Pages (from-to)132-140
Number of pages9
JournalNetworks
Volume70
Issue number2
DOIs
Publication statusPublished - 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

Fingerprint

Dive into the research topics of 'Bounds on the fault-diameter of graphs'. Together they form a unique fingerprint.

Cite this