Geodesic
Classification of graphs of diameter~$2$
Sibirskie èlektronnye matematičeskie izvestiâ, Tome 17 (2020), pp. 502-512.

Voir la notice de l'article provenant de la source Math-Net.Ru

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. 
@article{SEMR_2020_17_a65,
     author = {T. I. Fedoryaeva},
     title = {Classification of graphs of diameter~$2$},
     journal = {Sibirskie \`elektronnye matemati\v{c}eskie izvesti\^a},
     pages = {502--512},
     publisher = {mathdoc},
     volume = {17},
     year = {2020},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/SEMR_2020_17_a65/}
}
TY  - JOUR
AU  - T. I. Fedoryaeva
TI  - Classification of graphs of diameter~$2$
JO  - Sibirskie èlektronnye matematičeskie izvestiâ
PY  - 2020
SP  - 502
EP  - 512
VL  - 17
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/SEMR_2020_17_a65/
LA  - ru
ID  - SEMR_2020_17_a65
ER  - 
%0 Journal Article
%A T. I. Fedoryaeva
%T Classification of graphs of diameter~$2$
%J Sibirskie èlektronnye matematičeskie izvestiâ
%D 2020
%P 502-512
%V 17
%I mathdoc
%U http://geodesic.mathdoc.fr/item/SEMR_2020_17_a65/
%G ru
%F SEMR_2020_17_a65
T. I. Fedoryaeva. Classification of graphs of diameter~$2$. Sibirskie èlektronnye matematičeskie izvestiâ, Tome 17 (2020), pp. 502-512. http://geodesic.mathdoc.fr/item/SEMR_2020_17_a65/

[1] V.A. Emelichev, O.I. Melnikov, V.I. Sarvanov, R.I. Tyshkevich, Lectures on Graph Theory, B.I. Wissenschaftsverlag, Mannheim, 1994 | MR | Zbl

[2] T.I. Fedoryaeva, “The diversity vector of balls of a typical graph of small diameter”, Diskretn. Anal. Issled. Oper., 22:6 (2015), 43–54 | MR | Zbl

[3] T.I. Fedoryaeva, “Structure of the diversity vector of balls of a typical graph with given diameter”, Sib. Electron. Mat. Izv., 13 (2016), 375–387 | MR | Zbl

[4] T.I. Fedoryaeva, “Asymptotic approximation for the number of n-vertex graphs of given diameter”, J. Appl. Ind. Math., 11:2 (2017), 204–2014 | DOI | MR | Zbl

[5] D. Galvin, Three tutorial lectures on entropy and counting, 2014, arXiv: 1406.7872

[6] Ronald L. Graham, Donald E. Knuth, Oren Patashnik, Concrete Mathematics, Addison-Wesley, 1994 | MR | Zbl

[7] F. Harary, Graph Theory, Addison–Wesley, London, 1969 | MR | Zbl

[8] J.W. Moon, L. Moser, “Almost all (0,1) matrices are primitive”, Stud. Sci. Math. Hung., 1 (1966), 153–156 | MR | Zbl