A classification of graphs of diameter $2$
T. I. Fedoryaeva · Sibirskie Elektronnye Matematicheskie Izvestiya · 2020
The classification of graphs of diameter 2 by the number of pairs of diametral vertices contained in the graph is designed.All possible values of the parameters n and k are established for which there exists a n-vertex graph of diameter 2 that has exactly k pairs of diametral vertices.As a corollary, the smallest order of these graphs is found.Such graphs with a large number of vertices are also described and counted.In addition, for any fixed integer k ≥ 1 inside each distinguished class of n-vertex graphs of diameter 2 containing exactly k pairs of diametral vertices, a class of typical graphs is constructed.For the introduced classes, the almost all property is studied for any k = k(n) with the growth restriction under consideration, covering the case of a fixed integer k ≥ 1.As a consequence, it is proved that it is impossible to limit the number of pairs of diametral vertices by a given fixed integer k in order to obtain almost all graphs of diameter 2.