On vertex critical graphs with prescribed diameter
Louis Caccetta, Samy El-Batanouny, Jing Huang · Journal of Graph Theory · 2003
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′ ≤ 2D − 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