Maximal and Minimal Vertex-Critical Graphs of Diameter Two
Source: Journal of Combinatorial Theory, Series B, Volume 74, Number 2, November 1998 , pp. 311-325(15)
Publisher: Academic Press
Abstract: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 ½2-2 3/2+c1 edges, where c1 is some constant. We show that such a graph contains at most ½2-(2/2) 3/2+c2 edges, where c2 is some constant. We also construct, for each 5 except =6, a vertex-critical graph of diameter two on vertices with at most ½ (5-12) edges. We show that such a graph must contain at least ½ (5-29) edges. Copyright 1998 Academic Press.
Document Type: Research Article
Affiliations: 1: Department of Mathematics and Statistics, University of Victoria, Victoria, British Columbia, V8W 3P4, Canada 2: Department of Mathematics and Computer Science, Odense University, Odense, DK-5230, Denmark
Publication date: November 1, 1998