Hamilton cycles in weighted Erd\H{o}s-R\'enyi graphs

MaRDI QIDQ6356683zbMATH OpenFDO

Authors Tony Johansson

Publication date 22 December 2020

Abstract: Given a symmetric $nimesn$ matrix $P$ with $0leP(u,v)le1$, we define a random graph $G_{n,P}$ on $[n]$ by independently including any edge $u,v$ with probability $P(u,v)$. For $kge1$ let $mathcal{A}_k$ be the property of containing $lfloork/2floor$ 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}inmathcal{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 $muled(d/n{)}^{a}lpha$ for some constant $alpha>0$ has property $mathcal{A}_k$ as soon as it acquires minimum degree $k$ with high probability.

This page was built for publication: Hamilton cycles in weighted Erd\H{o}s-R\'enyi graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6356683)