Primitive diameter $2$-critical graphs


Jovan Radosavljević, Zoran Stanić, Miodrag Živković




We study diameter $2$-critical graphs (for short, D2C graphs), i.e., graphs of diameter $2$ whose diameter increases after removing any edge. Our results include structural considerations, new examples and a particular relationship with minimal $2$-self-centered graphs stating that these graph classes are almost identical. We pay an attention to primitive D2C graphs (PD2C graphs) which, by definition, have no two vertices with the same set of neighbours. It is known that a graph of diameter $2$ and order $n$, which has no dominating vertex, has at least $2n-5$ edges, and the graphs that attain this bound are also known. It occurs that exactly three of them are PD2C. The next natural step is to consider PD2C graphs with $2n-4$ edges. In this context, we determine an infinite family of PD2C graphs which, for every $n\geq 6$, contains exactly one graph with $2n-4$ edges. We also prove that there are exactly seven Hamiltonian PD2C graphs with the required number of edges. We show that for $n\leq 13$, there exists a unique PD2C graph with $2n-4$ edges that does not belong to the obtained family nor is Hamiltonian. It is conjectured that this is a unique example of such a graph.