Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6424127 | European Journal of Combinatorics | 2015 | 12 Pages |
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 Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Tomasz Åuczak, Åukasz Witkowski, Marcin Witkowski,