𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Minimum vertex-diameter-2-critical graphs

✍ Scribed by Ya-Chen Chen; Zoltán Füredi

Publisher
John Wiley and Sons
Year
2005
Tongue
English
Weight
182 KB
Volume
50
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

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

📜 SIMILAR VOLUMES

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

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 &

Vertex domination-critical graphs
Vertex domination-critical graphs
✍ Jason Fulman; Denis Hanson; Gary Macgillivray 📂 Article 📅 1995 🏛 John Wiley and Sons 🌐 English ⚖ 293 KB
Vertex domination-critical graphs
Vertex domination-critical graphs
✍ Robert C. Brigham; Phyllis Z. Chinn; Ronald D. Dutton 📂 Article 📅 1988 🏛 John Wiley and Sons 🌐 English ⚖ 303 KB
Kr-Free Uniquely Vertex Colorable Graphs
Kr-Free Uniquely Vertex Colorable Graphs with Minimum Possible Edges
✍ S. Akbari; V.S. Mirrokni; B.S. Sadjad 📂 Article 📅 2001 🏛 Elsevier Science 🌐 English ⚖ 112 KB

We construct counterexamples to the conjecture of Xu (1990, J. Combin. Theory Ser. B 50, 319 320) that every uniquely r-colorable graph of order n with exactly (r&1) n&( r2 ) edges must contain a K r . ## 2001 Academic Press Harary et al. [4] constructed uniquely r-colorable graphs containing no