Properties of Edge-Maximal $K$-Edge-Connected $D$-Critical Graphs

Abstract

An undirected graph of diameter $D$ is said to be $D$-critical if the addition of any edge decreases its diameter. The structure of $D$-critical graphs can be conveniently studied in terms of vertex sequences. Following on earlier results, we establish, in this paper, fundamental properties of $K$-edge-connected $D$-critical graphs for $K\ge 8$ and $D\ge 7$. In particular, we show that no vertex sequence corresponding to such a graph can contain an “internal” term less than $3$, and that no two non-adjacent internal terms can exceed $\text{K}-\lceil 2\sqrt{\text{K}}\rceil +1$. These properties will be used in forthcoming work to show that every subsequence (except at most one) of length three of the vertex sequence contains exactly $K+1$ vertices, a result which leads to a complete characterization of edge-maximal vertex sequences.