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

2020/01/15 by Johansson, Tony
#Combinatorics (math.CO) #FOS: Mathematics #Probability (math.PR)

paper · doi:10.48550/arxiv.2001.05258

Abstract

We consider the random graph G_n, \bf d chosen uniformly at random from the set of all graphs with a given sparse degree sequence \bf d. We assume \bf d has minimum degree at least 4, at most a power law tail, and place one more condition on its tail. For k≥ 2 define β_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, \bf d contains a Hamilton cycle reduces to calculating β₂(G_n, \bf d). If k≥ 2 and δ≥ k+2, the problem of determining if G_n, \bf d contains a k-factor reduces to calculating β_k(G_n, \bf d).

Related

• An almost linear time algorithm for finding Hamilton cycles in sparse random graphs with minimum degree at least three
• On the number of Hamilton cycles in sparse random graphs
• Random perturbation of sparse graphs
• Hamiltonicity of Sparse Pseudorandom Graphs
• Random graph's Hamiltonicity is strongly tied to its minimum degree