|
This article is cited in 1 scientific paper (total in 1 paper)
Discrete mathematics and mathematical cybernetics
Classification of graphs of diameter $2$
T. I. Fedoryaeva Sobolev Institute of Mathematics, 4, Koptyuga ave., Novosibirsk, 630090, Russia
Abstract:
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\geq 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\geq 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$.
Keywords:
graph, diameter $2$, diametral vertices, typical graphs, almost all graphs.
Received January 19, 2020, published April 6, 2020
Citation:
T. I. Fedoryaeva, “Classification of graphs of diameter $2$”, Sib. Èlektron. Mat. Izv., 17 (2020), 502–512
Linking options:
https://www.mathnet.ru/eng/semr1226 https://www.mathnet.ru/eng/semr/v17/p502
|
|