Diameter vulnerability of graphs (Q800372): Difference between revisions
From MaRDI portal
Removed claims |
ReferenceBot (talk | contribs) Changed an Item |
||
(2 intermediate revisions by 2 users not shown) | |||
Property / author | |||
Property / author: Claudine Peyrat / rank | |||
Normal rank | |||
Property / reviewed by | |||
Property / reviewed by: Wai-Kai Chen / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Diameter bounds for altered graphs / rank | |||
Normal rank |
Latest revision as of 15:49, 14 June 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Diameter vulnerability of graphs |
scientific article |
Statements
Diameter vulnerability of graphs (English)
0 references
1984
0 references
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.
0 references
vulnerability
0 references
edge-connectivity
0 references
diameter
0 references