Diameter vulnerability of graphs
type: Item
instance of: scholarly article
title: Diameter vulnerability of graphs
zbMATH Open document ID: 0549.05036
DOI: 10.1016/0166-218X(84)90024-6
published in: Discrete Applied Mathematics
publication date: 1984-01-01T00:00:00Z
review text: Let f(t,D) denote the maximum diameter of a graph obtained from a \((t+1)\)-edge-connected graph of diameter D by deleting t edges. In the paper it is shown that for \(D=2\) and \(D=3\), \(f(t,2)=4\), \(3\sqrt{2t}-3\leq f(t,3)\leq 3\sqrt{2t}+4.\) In the case of a \((t+1)\)-arc-connected digraph of order n and diameter at least 3, the maximum diameter for a digraph obtained from this digraph by deleting t arcs is \(n-2t+1\), and this bound can be achieved. For \(D=2\), the maximum diameter of the resulting digraph is 4.
Mathematics Subject Classification ID: 05C35
Mathematics Subject Classification ID: 05C40
Mathematics Subject Classification ID: 05C20
zbMATH DE Number: 3875320
zbMATH Keywords: vulnerability
zbMATH Keywords: edge-connectivity
zbMATH Keywords: diameter
author: Claudine Peyrat
reviewed by: Wai-Kai Chen
MaRDI profile type: Publication
cites work: Diameter bounds for altered graphs
description: scientific article; zbMATH DE number 3875320