Are almost all n-vertex graphs of given diameter Hamiltonian?
Are almost all $n$-vertex graphs of given diameter Hamiltonian?
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.