A condition for Hamiltonicity in Sparse Random Graphs with a Fixed Degree Sequence

Abstract

We consider the random graph $G_{n,\mathbf{d}}$ chosen uniformly at random from the set of all graphs with a given sparse degree sequence $\mathbf{d}$. We assume $\mathbf{d}$ has minimum degree at least 4, at most a power law tail, and place one more condition on its tail. For $k\ge 2$ define ${\beta }_k(G)=\max e(A,B)+k(|A|-|B|)-d(A)$, with the maximum taken over disjoint vertex sets $A,B$. It is shown that the problem of determining if $G_{n,\mathbf{d}}$ contains a Hamilton cycle reduces to calculating ${\beta }_2(G_{n,\mathbf{d}})$. If $k\ge 2$ and $\delta \ge k+2$, the problem of determining if $G_{n,\mathbf{d}}$ contains a $k$-factor reduces to calculating ${\beta }_k(G_{n,\mathbf{d}})$.