Hamilton cycles in weighted Erdős-Rényi graphs

Abstract

Given a symmetric $n\times n$ matrix $P$ with $0\le P(u,v)\le 1$, we define a random graph $G_{n,P}$ on $[n]$ by independently including any edge $\{u,v\}$ with probability $P(u,v)$. For $k\ge 1$ let ${\mathcal{A}}_k$ be the property of containing $\lfloor k/2\rfloor$ Hamilton cycles, and one perfect matching if $k$ is odd, all edge-disjoint. With an eigenvalue condition on $P$, and conditions on its row sums, $G_{n,P}\in {\mathcal{A}}_k$ happens with high probability if and only if $G_{n,P}$ has minimum degree $k$ whp. We also provide a hitting time version. As a special case, the random graph process on pseudorandom $(n,d,\mu )$-graphs with $\mu \le d(d/n{)}^{\alpha }$ for some constant $\alpha >0$ has property ${\mathcal{A}}_k$ as soon as it acquires minimum degree $k$ with high probability.