Hamilton cycles in random lifts of directed graphs

被引:4
作者
Chebolu, Prasad [1 ]
Frieze, Alan [1 ]
机构
[1] Carnegie Mellon Univ, Dept Math, Pittsburgh, PA 15213 USA
关键词
digraph; random; lifts; Hamilton cycle;
D O I
10.1137/060670808
中图分类号
O29 [应用数学];
学科分类号
070104 ;
摘要
An n-lift of a digraph K is a digraph with a vertex set V (K) x [n], and for each directed edge (i, j). E(K) there is a perfect matching between fibers {i} x [n] and {j} x [n], with edges directed from fiber i to fiber j. If these matchings are chosen independently and uniformly at random, then we say that we have a random n-lift. We show that if h is sufficiently large, then a random n-lift of the complete digraph (K) over right arrow (h) is a Hamiltonian whp.
引用
收藏
页码:520 / 540
页数:21
相关论文
共 14 条
[1]   Random lifts of graphs: Edge expansion [J].
Amit, A ;
Linial, N .
COMBINATORICS PROBABILITY & COMPUTING, 2006, 15 (03) :317-332
[2]   Random graph coverings I: General theory and graph connectivity [J].
Amit, A ;
Linial, N .
COMBINATORICA, 2002, 22 (01) :1-18
[3]   Random lifts of graphs: Independence and chromatic number [J].
Amit, A ;
Linial, N ;
Matousek, J .
RANDOM STRUCTURES & ALGORITHMS, 2002, 20 (01) :1-22
[4]  
[Anonymous], 2011, Random Graphs
[5]   Hamilton cycles in random lifts of graphs [J].
Burgin, K. ;
Chebolu, P. ;
Cooper, C. ;
Frieze, A. M. .
EUROPEAN JOURNAL OF COMBINATORICS, 2006, 27 (08) :1282-1293
[6]   HAMILTON CYCLES IN A CLASS OF RANDOM DIRECTED-GRAPHS [J].
COOPER, C ;
FRIEZE, A .
JOURNAL OF COMBINATORIAL THEORY SERIES B, 1994, 62 (01) :151-163
[7]  
Cooper C, 2000, RANDOM STRUCT ALGOR, V16, P369, DOI 10.1002/1098-2418(200007)16:4<369::AID-RSA6>3.0.CO
[8]  
2-J
[9]  
Cooper C., 1994, COMBINAT PROBAB COMP, V3, P39
[10]   Approximately counting Hamilton paths and cycles in dense graphs [J].
Dyer, M ;
Frieze, A ;
Jerrum, M .
SIAM JOURNAL ON COMPUTING, 1998, 27 (05) :1262-1272