𝔖 Bobbio Scriptorium
✦   LIBER   ✦

A characterization of -free, diameter-2-critical graphs

✍ Scribed by Haynes, Teresa W.; Henning, Michael A.

Book ID
122268143
Publisher
Elsevier Science
Year
2014
Tongue
English
Weight
367 KB
Volume
169
Category
Article
ISSN
0166-218X

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

On diameter 2-critical graphs
On diameter 2-critical graphs
✍ Genghua Fan πŸ“‚ Article πŸ“… 1987 πŸ› Elsevier Science 🌐 English βš– 296 KB

A graph is diameter 2-critical if the graph has diameter 2 and the deletion of any edge increases its diameter. We prove that if G is diameter 2-critical graph on n vertices and e edges, then (i) e ~< [14n2 ] for n <~ 24, and (ii) e < !4n2 + (n 2 -16.2 n + 56)/320 (<0.2532 n2), for n/> 25.

On Critical Graphs of Diameter 2
On Critical Graphs of Diameter 2
✍ U. S. R. Murty πŸ“‚ Article πŸ“… 1968 πŸ› Mathematical Association of America 🌐 English βš– 337 KB
Diameter-critical graphs
Diameter-critical graphs
✍ N. P. Khomenko; N. A. Ostroverkhii πŸ“‚ Article πŸ“… 1971 πŸ› Springer 🌐 English βš– 556 KB
Minimum vertex-diameter-2-critical graph
Minimum vertex-diameter-2-critical graphs
✍ Ya-Chen Chen; ZoltΓ‘n FΓΌredi πŸ“‚ Article πŸ“… 2005 πŸ› John Wiley and Sons 🌐 English βš– 182 KB πŸ‘ 1 views

## Abstract We prove that the minimum number of edges in a vertex‐diameter‐2‐critical graph on __n__ β‰₯ 23 vertices is (5__n__β€‰βˆ’β€‰17)/2 if __n__ is odd, and is (5__n__/2)β€‰βˆ’β€‰7 if __n__ is even. Β© 2005 Wiley Periodicals, Inc. J Graph Theory