Hamilton Cycles in Random Lifts of Graphs

الأصل · EN

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.