Are almost all n-vertex graphs of given diameter Hamiltonian?

Are almost all $n$-vertex graphs of given diameter Hamiltonian?

Fedoryaeva T. I.
Siberian Electronic Mathematical Reports, 21, 2, pp. 1549-1561 (2024)

УДК 519.174.2, 519.175.4 
DOI: 10.33048/semi.2024.21.098  
MSC 05C45, 05C80


Abstract: 

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.