✦ LIBER ✦

On vertex critical graphs with prescribed diameter

✍ Scribed by L. Caccetta; S. EL-Batanouny; J. Huang

Publisher: John Wiley and Sons
Year: 2003
Tongue: English
Weight: 167 KB
Volume: 43
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.10108

No coin nor oath required. For personal study only.

✦ Synopsis

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), 193—198] conjectured that if G is a v^+^‐critical graph of diameter D, then D′ ≤ 2__D__ − 1. They verified their conjecture for D = 2 and 3. In this paper we show that this conjecture is false for all D ≥ 4 and establish a sharp upper bound for D′. More specifically, we prove that D′ ≤ 3D − 3 for D = 4, 6, 8; and $D^\prime \le 2D + 3 \left\lfloor {{1 \over 2}(D + 1)} \right\rfloor! - 8$; otherwise. © 2003 Wiley Periodicals, Inc. J Graph Theory 43: 117–131, 2003

📜 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

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 &

On graphs with prescribed median I

✍ G. R. T. Hendry 📂 Article 📅 1985 🏛 John Wiley and Sons 🌐 English ⚖ 202 KB 👁 1 views

The distance of a vertex u in a connected graph H is the sum of all the distances from u to the other vertices of H. The median M(H) of H is the subgraph of H induced by the vertices of minimum distance. For any graph G, let f ( G ) denote the minimum order of a connected graph H satisfying M(H) = G

On iterated clique graphs with increasin

On iterated clique graphs with increasing diameters

✍ C. Peyrat; D. F. Rall; P. J. Slater 📂 Article 📅 1986 🏛 John Wiley and Sons 🌐 English ⚖ 210 KB 👁 1 views

We examine the problem of finding a graph G whose nth iterated clique graph has diameter equal to the diameter of G plus n.

Infinite families of crossing-critical g

Infinite families of crossing-critical graphs with prescribed average degree and crossing number

✍ Drago Bokal 📂 Article 📅 2010 🏛 John Wiley and Sons 🌐 English ⚖ 242 KB 👁 1 views

## Abstract Širáň constructed infinite families of __k__‐crossing‐critical graphs for every __k__⩾3 and Kochol constructed such families of simple graphs for every __k__⩾2. Richter and Thomassen argued that, for any given __k__⩾1 and __r__⩾6, there are only finitely many simple __k__‐crossing‐criti

A note on graphs with diameter-preservin

A note on graphs with diameter-preserving spanning trees

✍ Fred Buckley; Martin Lewinter 📂 Article 📅 1988 🏛 John Wiley and Sons 🌐 English ⚖ 182 KB 👁 1 views

The distance between a pair of vertices u, u in a graph G is the length of a shortest path joining u and u. The diameter diam(G) of G is the maximum distance between all pairs of vertices in G. A spanning tree Tof G is diameter preserving if diam(T) = diam(G). In this note, we characterize graphs th