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\geq8\) and \(D\geq7\). 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.