Two types of matchings extend to Hamiltonian cycles in hypercubes

被引:0
作者
Wang, Fan [1 ,2 ]
Zhang, Heping [1 ]
机构
[1] Lanzhou Univ, Sch Math & Stat, Lanzhou 730000, Gansu, Peoples R China
[2] Nanchang Univ, Dept Math, Nanchang 330000, Jiangxi, Peoples R China
关键词
Hypercube; Hamiltonian cycle; Matching; Perfect matching; GRAPHS; EDGES;
D O I
暂无
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
Ruskey and Savage asked the following question: For n >= 2, does every matching in Q(n) extend to a Hamiltonian cycle in Q(n)? Fink showed that the answer is yes for every perfect matching, thereby proving Kreweras' conjecture. In this paper, we prove for n >= 3 that every matching in Q(n) not covering exactly two vertices at distance 3 extends to a Hamiltonian cycle in Q(n). An edge in Q(n) is an i-edge if its endpoints differ in the ith position. We show for n >= 2 that every matching in Q(n) consisting of edges in at most four types extends to a Hamiltonian cycle in Q(n).
引用
收藏
页码:269 / 283
页数:15
相关论文
共 12 条