Vulnerability in graphs of diameter four (Q1310232): Difference between revisions
From MaRDI portal
Changed an Item |
ReferenceBot (talk | contribs) Changed an Item |
||
(One intermediate revision by one other user not shown) | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4146750 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On a measure of communication network vulnerability / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Graphs as models of communication network vulnerability: Connectivity and persistence / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Counterexamples to theorems of Menger type for the diameter / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Parallel concepts in graph theory / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Geodetic connectivity of graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Mengerian theorems for paths of bounded length / rank | |||
Normal rank |
Revision as of 12:09, 22 May 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Vulnerability in graphs of diameter four |
scientific article |
Statements
Vulnerability in graphs of diameter four (English)
0 references
28 June 1994
0 references
\textit{J. Hartman} and \textit{I. Rubin} [Theor. Appl. Graphs, Proc. Kalamazoo 1976, Lect. Notes Math. 642, 247-254 (1976; Zbl 0371.05019)] showed for graphs with diameter at most 3 that the minimum number of edges whose deletion increases the diameter equals the minimum, over all pairs of vertices \(u,v\), of the cardinality of a largest set of edge disjoint \(u\)- \(v\) paths. This result does not hold for graphs of diameter 4 or greater. The authors show for graphs \(G\) of diameter 4 that the minimum number of edges whose deletion increases the diameter of \(G\) is 2 if and only if for all pairs of vertices \(u,v\) of \(G\) either there exist two edge disjoint \(u\)-\(v\) paths with diameter at most the diameter of \(G\) or else \(G\) contains an induced subgraph isomorphic to the cactus consisting of three triangles in which the distance between \(u\) and \(v\) is 3.
0 references
diameter
0 references
distance
0 references