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>=4 are nonHamiltonian graphs. All found typical Hamiltonian properties of n-vertex graphs of a fixed diameter k>=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.