Hamilton Cycles in Random Lifts of Graphs

2013/06/09 by Tomasz Łuczak, Łuczak, Tomasz, Łukasz Witkowski +3
Mathematics · #05C45 #05C80 #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Limits and Structures in Graph Theory #Stochastic processes and statistical mechanics

paper · pdf · doi:10.48550/arxiv.1306.2057

openalex publication_date 2013/06/09 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

For a graph G the random n-lift of G is obtained by replacing each of its vertices by a set of n vertices, and joining a pair of sets by a random matching whenever the corresponding vertices of G are adjacent. We show that asymptotically almost surely the random lift of a graph G is hamiltonian, provided G has the minimum degree at least 5 and contains two disjoint Hamiltonian cycles whose union is not a bipartite graph.

Related

• High powers of Hamiltonian cycles in randomly augmented graphs
• Random graph's Hamiltonicity is strongly tied to its minimum degree
• Hamilton cycles in regular graphs perturbed by a random 2-factor
• Hamiltonicity of the random geometric graph
• Powers of Hamiltonian cycles in randomly augmented Dirac graphs -- the complete collection