Vulnerability in graphs of diameter four
\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.
- Counterexamples to theorems of Menger type for the diameter
- Geodetic connectivity of graphs
- Graphs as models of communication network vulnerability: Connectivity and persistence
- scientific article; zbMATH DE number 3577229 (Why is no real title available?)
- Mengerian theorems for paths of bounded length
- On a measure of communication network vulnerability
- Parallel concepts in graph theory
- Diameter-vulnerability of large bipartite digraphs
- A note on vulnerability in graphs of diameter five(II)
- Extremal graphs of diameter at most 6 after deleting any vertex
- Realizability ofp-point,q-line graphs with prescribed maximum degree and line connectivity or minimum degree
- Vulnerability in graphs of diameter five
- Some extended results on diameter-stable graphs
This page was built for publication: Vulnerability in graphs of diameter four
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1310232)
