Hamilton cycles in random lifts of graphs |
| |
Authors: | K Burgin P Chebolu C Cooper AM Frieze |
| |
Institution: | aDepartment of Mathematical Sciences, Carnegie Mellon University, Pittsburgh, PA 15213, USA;bSchool of Mathematical Sciences, University of North London, London N7 8DB, UK |
| |
Abstract: | An n-lift of a graph K is a graph with vertex set V(K)×n], and for each edge (i,j) E(K) there is a perfect matching between {i}×n] and {j}×n]. If these matchings are chosen independently and uniformly at random then we say that we have a random n-lift. We show that there are constants h1,h2 such that if h≥h1 then a random n-lift of the complete graph Kh is hamiltonian and if h≥h2 then a random n-lift of the complete bipartite graph Kh,h is hamiltonian . |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|