Vulnerability in graphs of diameter four
type: Item
instance of: scholarly article
title: Vulnerability in graphs of diameter four
zbMATH Open document ID: 0791.05033
DOI: 10.1016/0895-7177(93)90254-V
author: Geoffrey Exoo
author: Frank Harary
author: Chengde Xu
published in: Mathematical and Computer Modelling
publication date: 1994-06-28T00:00:00Z
review text: \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.
Mathematics Subject Classification ID: 05C12
zbMATH DE Number: 475041
zbMATH Keywords: diameter
zbMATH Keywords: distance
reviewed by: R. C. Entringer
MaRDI profile type: Publication
cites work: Q4146750
cites work: On a measure of communication network vulnerability
cites work: Graphs as models of communication network vulnerability: Connectivity and persistence
cites work: Counterexamples to theorems of Menger type for the diameter
cites work: Parallel concepts in graph theory
cites work: Geodetic connectivity of graphs
cites work: Mengerian theorems for paths of bounded length
full work available at URL: 0895-7177(93)90254-v
OpenAlex ID: W2088617487
description: scientific article; zbMATH DE number 475041