Geodesic
Are almost all $n$-vertex graphs of given diameter Hamiltonian?
Sibirskie èlektronnye matematičeskie izvestiâ, Tome 21 (2024) no. 2, pp. 1549-1561 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

Typical Hamiltonian properties of the class of $n$-vertex graphs of a fixed diameter $k$ are studied. A new class of typical $n$-vertex graphs of a given diameter is constructed. The question of S.V. Avgustinovich on the Hamiltonian property of almost all such $n$-vertex graphs has been solved. It is proved that almost all $n$-vertex graphs of fixed diameter $k=1,2,3$ are Hamiltonian, while almost all $n$-vertex graph of fixed diameter $k\geq 4$ are nonHamiltonian graphs. All found typical Hamiltonian properties of $n$-vertex graphs of a fixed diameter $k\geq 1$ are also typical for connected graphs of diameter at least $k$, as well as for graphs (not necessarily connected) containing the shortest path of length at least $k$.
Keywords: graph, Hamiltonian graph, Hamiltonian cycle, diameter, typical graphs, almost all graphs. 
@article{SEMR_2024_21_2_a31,
     author = {T. I. Fedoryaeva},
     title = {Are almost all $n$-vertex graphs of given diameter {Hamiltonian?}},
     journal = {Sibirskie \`elektronnye matemati\v{c}eskie izvesti\^a},
     pages = {1549--1561},
     year = {2024},
     volume = {21},
     number = {2},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/SEMR_2024_21_2_a31/}
}
TY  - JOUR
AU  - T. I. Fedoryaeva
TI  - Are almost all $n$-vertex graphs of given diameter Hamiltonian?
JO  - Sibirskie èlektronnye matematičeskie izvestiâ
PY  - 2024
SP  - 1549
EP  - 1561
VL  - 21
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/SEMR_2024_21_2_a31/
LA  - en
ID  - SEMR_2024_21_2_a31
ER  - 
%0 Journal Article
%A T. I. Fedoryaeva
%T Are almost all $n$-vertex graphs of given diameter Hamiltonian?
%J Sibirskie èlektronnye matematičeskie izvestiâ
%D 2024
%P 1549-1561
%V 21
%N 2
%U http://geodesic.mathdoc.fr/item/SEMR_2024_21_2_a31/
%G en
%F SEMR_2024_21_2_a31
T. I. Fedoryaeva. Are almost all $n$-vertex graphs of given diameter Hamiltonian?. Sibirskie èlektronnye matematičeskie izvestiâ, Tome 21 (2024) no. 2, pp. 1549-1561. http://geodesic.mathdoc.fr/item/SEMR_2024_21_2_a31/

[1] V. Chv$\acute{a}$tal, P. Erd$\ddot{o}$s, “A note on Hamiltonian circuits”, Discrete Math., 2 (1972), 111–113 | DOI | Zbl

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

[3] Diskretn. Anal. Issled. Oper., 2:3 (1995), 49–67 | DOI | Zbl

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

[5] Diskretn. Anal. Issled. Oper., 24:2 (2017), 68–86 | DOI | Zbl

[6] T.I. Fedoryaeva, “On radius and typical properties of $n$-vertex graphs of given diameter”, Sib. Èlektron. Mat. Izv., 18:1 (2021), 345–357 | DOI | Zbl

[7] T.I. Fedoryaeva, “Logarithmic asymptotics of the number of central vertices of almost all $n$-vertex graphs of diameter $k$”, Sib. Èlektron. Mat. Izv., 19:2 (2022), 747–761 | DOI | Zbl

[8] T.I. Fedoryaeva, “Typical metric properties of $n$-vertex graphs of given diameter”, Discrete mathematics and its applications, XIV International Scientific Seminar named after Academician O.B. Lupanov, 2022, 21–33 | DOI

[9] R.J. Gould, “Updating the Hamiltonian Problem — A Survey”, J. Graph Theory, 15:2 (1991), 121–157 | DOI | Zbl

[10] R. L. Graham, D. E. Knuth, O. Patashnik, Concrete Mathematics, Addison-Wesley, 1994 | Zbl

[11] Graph online, https://graphonline.ru

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

[13] M. Jixiang, H. Qiongxiang, “Almost all Cayley graphs are hamiltonian”, Acta Math. Sin., New Ser., 12:2 (1996), 151–155 | DOI | Zbl

[14] J. Soviet Math., 39:1 (1987), 2476–2508 | DOI | Zbl | Zbl

[15] J.W. Moon, “Almost all graphs have spanning cycle”, Canad. Math. Bull., 15 (1972), 39–41 | DOI | Zbl

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

[17] Dokl. Akad. Nauk SSSR, 194:6 (1970), 1269–1271 | Zbl

[18] R.W. Robinson, N.C. Wormald, “Almost all regular graphs are hamiltonian”, Random Struct. Algorithms, 5:2 (1994), 363–374 | DOI | Zbl