Distance critical graphs (Q6942795)

A graph is distance critical if deleting any one vertex results in a change to some pairwise distance. These graphs were first studied by \textit{P. Erdős} and \textit{E. Howorka} [Ars Comb. 9, 249--251 (1980; Zbl 0501.05043)], this paper is the first in which distance critical graphs are systematically investigated. Several structural properties are obtained, and distance critical Cartesian, direct, and strong products characterized. It is proved that if \(n\ge 5\), then the maximum \(d\) for which there is a \(d\)-regular distance critical graph is \(\lfloor (n-1)/4\rfloor + \lfloor n/4\rfloor\). The maximum possible clique number among distance critical graphs on a given number of vertices is estimated, and it is proved that every graph on \(n\) vertices is an induced subgraph of some distance critical graph on \(n + O(\sqrt{n})\) vertices.