A type of perfect matchings extend to hamiltonian cycles in k-ary n-cubes
A type of perfect matchings extend to hamiltonian cycles in k-ary n-cubes
复制标题
一种完美匹配扩展到 k 元 n 立方体中的哈密顿循环
DOI：
10.1016/j.tcs.2018.03.029
复制
发表时间：
2018
影响因子：
1.1
通讯作者：
Wuyang Sun
中科院分区：
文献类型：
--
作者：
Fan Wang;Wuyang Sun
Kreweras证明了超立方体Qn（n≥ 2）中的每一个完美匹配都可扩张到Qn的一个Hamilton圈.芬克证实了这个猜想。k元n方体Q n k是超立方体的推广。然而，类似的结果并不一定适用于Q n k。我们可以找到一个完美的匹配在Q2 6，这是不包含在任何哈密尔顿圈Q2 6。本文研究了Qnk中通过完美匹配的Hamilton圈的存在性。对n≥ 2和k≥ 6的偶数，证明了Qnk中的每一个由同维边组成的完美匹配都可以扩张为Qnk的一个Hamilton圈.
Kreweras conjectured that every perfect matching in a hypercube Q n for n≥ 2 extends to a hamiltonian cycle of Q n. Fink confirmed the conjecture to be true. The k-ary n-cube Q n k is a generalization of the hypercube. However, the analogous result does not necessarily hold for Q n k. We can find a perfect matching in Q 2 6 which is not contained in any hamiltonian cycle of Q 2 6. In this paper, we investigate the existence of a hamiltonian cycle passing through a perfect matching in Q n k. For an integer n≥ 2 and an even integer k≥ 6, we prove that every perfect matching in Q n k consisting of edges in the same dimension can be extended to a hamiltonian cycle of Q n k.