Article ID Journal Published Year Pages File Type
6424127 European Journal of Combinatorics 2015 12 Pages PDF
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
, , ,