Vulnerability in graphs of diameter four (Q1310232): Difference between revisions

\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.