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. |
Year | DOI | Venue |
---|---|---|
2015 | 10.1016/j.ejc.2015.03.001 | European Journal of Combinatorics |
Field | DocType | Volume |
Discrete mathematics,Wheel graph,Random regular graph,Combinatorics,Random graph,Bound graph,Graph power,Cycle graph,Factor-critical graph,Mathematics,Path graph | Journal | 49 |
Issue | ISSN | Citations |
C | 0195-6698 | 0 |
PageRank | References | Authors |
0.34 | 10 | 3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Tomasz Łuczak | 1 | 225 | 40.26 |
łukasz witkowski | 2 | 0 | 0.34 |
Marcin Witkowski | 3 | 8 | 4.79 |