𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Vulnerability in graphs of diameter four

✍ Scribed by Geoffrey Exoo; Frank Harary; Cheng-De Xu

Publisher
Elsevier Science
Year
1993
Tongue
English
Weight
285 KB
Volume
17
Category
Article
ISSN
0895-7177

No coin nor oath required. For personal study only.

✦ Synopsis

The analogue of Menger's Theorem on connectivity has been investigated for graphs of low diameter in which the removal of a set of lines increases the diameter. When the diameter is at most three, such a theorem has been proven already. Also, examples have been constructed to show that the result does not always hold for graphs of diameter four or more. The line persistence of a graph is the minimum number of lines which must be removed to increase its diameter. Our present purpose is to characterize graphs of diameter four having two as the line persistence.

πŸ“œ SIMILAR VOLUMES

Diameter vulnerability of graphs
Diameter vulnerability of graphs
✍ C. Peyrat πŸ“‚ Article πŸ“… 1984 πŸ› Elsevier Science 🌐 English βš– 344 KB
Diameter vulnerability of GC graphs
Diameter vulnerability of GC graphs
✍ J. GΓ³mez; I. Pelayo; C. Balbuena πŸ“‚ Article πŸ“… 2003 πŸ› Elsevier Science 🌐 English βš– 469 KB

Concern over fault tolerance in the design of interconnection networks has stimulated interest in ΓΏnding large graphs with maximum degree and diameter D such that the subgraphs obtained by deleting any set of s vertices have diameter at most D , this value being close to D or even equal to it. This

Antipodal distance-regular graphs of dia
Antipodal distance-regular graphs of diameter four and five
✍ Tilla Schade πŸ“‚ Article πŸ“… 1999 πŸ› John Wiley and Sons 🌐 English βš– 179 KB πŸ‘ 2 views

An antipodal distance-regular graph of diameter four or five is a covering graph of a connected strongly regular graph. We give existence conditions for these graphs and show for some types of strongly regular graphs that no nontrivial covers exist.

Nonexistence of some Antipodal Distance-
Nonexistence of some Antipodal Distance-regular Graphs of Diameter Four
✍ Aleksandar JuriΕ‘iΔ‡; Jack Koolen πŸ“‚ Article πŸ“… 2000 πŸ› Elsevier Science 🌐 English βš– 160 KB

We find an inequality involving the eigenvalues of a regular graph; equality holds if and only if the graph is strongly regular. We apply this inequality to the first subconstituents of a distance-regular graph and obtain a simple proof of the fundamental bound for distance-regular graphs, discovere

Diameter vulnerability of iterated line
Diameter vulnerability of iterated line digraphs
✍ C. PadrΓ³; P. Morillo πŸ“‚ Article πŸ“… 1996 πŸ› Elsevier Science 🌐 English βš– 823 KB

Because of their good properties, iterated line digraphs (specially Kautz and de Bruijn digraphs) have been considered to design interconnection networks. The diameter-vulnerability of a digraph is the maximum diameter of the subdigraphs obtained by deleting a fixed number of vertices or arcs. For a