✦ LIBER ✦

Maximal and Minimal Vertex-Critical Graphs of Diameter Two

✍ Scribed by Jing Huang; Anders Yeo

Publisher: Elsevier Science
Year: 1998
Tongue: English
Weight: 446 KB
Volume: 74
Category: Article
ISSN: 0095-8956
DOI: 10.1006/jctb.1998.1852

No coin nor oath required. For personal study only.

✦ Synopsis

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 & vertices with at most 1 2 (5&&12) edges. We show that such a graph must contain at least 1 2 (5&&29) edges.

for every v # V(G ).

📜 SIMILAR VOLUMES

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

Reduced graphs of diameter two

✍ Hong-Jian Lai 📂 Article 📅 1990 🏛 John Wiley and Sons 🌐 English ⚖ 444 KB

## Abstract A graph __H__ is __collapsible__ if for every subset X ⊆ __V(H), H__ has a spanning connected subgraph whose set of odd‐degree vertices is X. In any graph __G__ there is a unique collection of maximal collapsible subgraphs, and when all of them are contracted, the resulting contraction

Large Cayley graphs and vertex-transitiv

Large Cayley graphs and vertex-transitive non-Cayley graphs of given degree and diameter

✍ Heather Macbeth; Jana Šiagiová; Jozef Širáň; Tomáš Vetrík 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 128 KB

## Abstract For any __d__⩾5 and __k__⩾3 we construct a family of Cayley graphs of degree __d__, diameter __k__, and order at least __k__((__d__−3)/3)^__k__^. By comparison with other available results in this area we show that our family gives the largest currently known Cayley graphs for a wide ra

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

Extremal graphs of diameter at most 6 af

Extremal graphs of diameter at most 6 after deleting any vertex

✍ Yoko Usami 📂 Article 📅 1985 🏛 John Wiley and Sons 🌐 English ⚖ 489 KB 👁 1 views

Suppose G is a graph of n vertices and diameter at most d having the property that, after deleting any vertex, the resulting subgraph has diameter at most 6. Then G contains at least max{n. r(4n -8)/31} edges if 4 s d s 6 . ## 1. Introduction We consider finite undirected simple graphs. (Terminolo