Maximal and Minimal Vertex-Critical Graphs of Diameter Two

AbstractA 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 12ν2−2ν3/2+c1νedges, wherec1is some constant. We show that such a graph contains at most 12ν2−(2/2)ν3/2+c2νedges, wherec2is some constant. We also construct, for eachν⩾5 exceptν=6, a vertex-critical graph of diameter two onνvertices with at most 12 (5ν−12) edges. We show that such a graph must contain at least 12 (5ν−29) edges