✦ LIBER ✦

On diameter 2-critical graphs

✍ Scribed by Genghua Fan

Publisher: Elsevier Science
Year: 1987
Tongue: English
Weight: 296 KB
Volume: 67
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(87)90174-9

No coin nor oath required. For personal study only.

✦ Synopsis

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.

📜 SIMILAR VOLUMES

On diameter critical graphs

✍ Louis Caccetta; Roland Häggkvist 📂 Article 📅 1979 🏛 Elsevier Science 🌐 English ⚖ 520 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

On vertex critical graphs with prescribe

On vertex critical graphs with prescribed diameter

✍ L. Caccetta; S. EL-Batanouny; J. Huang 📂 Article 📅 2003 🏛 John Wiley and Sons 🌐 English ⚖ 167 KB 👁 1 views

## Abstract Let __G__ be connected simple graph with diameter __d__(__G__). __G__ is said __v__^+^‐critical if __d__(__G__−__v__) is greater than __d__(__G__) for every vertex __v__ of __G__. Let D′ = max {__d__(__G__−__v__) : __v__ ∈ __V__(__G__)}. Boals et al. [Congressus Numerantium 72 (1990), 1

The diameter of domination k-critical gr

The diameter of domination k-critical graphs

✍ Odile Favaron; David P. Sumner; Ewa Wojcicka 📂 Article 📅 1994 🏛 John Wiley and Sons 🌐 English ⚖ 525 KB

## Abstract A graph is __k__‐domination‐critical if γ(__G) = k__, and for any edge __e__ not in __G__, γ(__G + e) = k__ − 1. In this paper we show that the diameter of a domination __k__‐critical graph with __k__ ≧ 2 is at most 2__k__ − 2. We also show that for every __k__ ≧ 2, there is a __k__‐dom

Note: The diameter of edge domination cr

Note: The diameter of edge domination critical graphs

✍ Matteo Paris 📂 Article 📅 1994 🏛 John Wiley and Sons 🌐 English ⚖ 111 KB

Maximal and Minimal Vertex-Critical Grap

Maximal and Minimal Vertex-Critical Graphs of Diameter Two

✍ Jing Huang; Anders Yeo 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 446 KB

A graph is vertex-critical if deleting any vertex increases its diameter. We construct, for each & 5 except &=6, a vertex-critical graph of diameter two on & vertices with at least , where c 2 is some constant. We also construct, for each & 5 except &=6, a vertex-critical graph of diameter two on &