Hamiltonicity of inhomogeneous random graphs

Abstract

We provide a complete characterization of those graphons $W$ for which the inhomogeneous random graph $G(n,W)$ is asymptotically almost surely Hamiltonian. The characterization involves three conditions. Two of them constitute the characterization of $G(n,W)$ being a.a.s. connected, as was shown recently by Hladký and Viswanathan. The third condition captures a geometric obstacle which prevents $G(n,W)$ from having perfect fractional matchings.

32 pages, 2 figure