超立方中匹配的哈密尔顿圈扩张性质

Ruskey 和 Savage 在 1993 年提出了如下问题: 当 n 大于 1 时, n 维超立方的每一个匹配能否扩张成一个哈密尔顿圈? Kreweras 猜想: 当 n 大于 1 时, n 维超立方的每一个完美匹配可以扩张成一个哈密尔顿圈. Fink 证实了 Kreweras 的猜想的正确性. k 元 n 立方是超立方的一种推广. 申请者在博士期间的工作已经表明 k 元 n 立方的完美匹配不一定能扩张成哈密尔顿圈, 这不同于超立方中完美匹配均可扩的结果. 本项目研究超立方中匹配的哈密尔顿圈扩张性质和 k 元 n 立方中完美匹配的哈密尔顿圈扩张性质. 具体地研究超立方中大小为线性型的匹配与大小为指数型的匹配的哈密尔顿圈扩张问题, 刻画其中可扩成哈密尔顿圈的匹配需满足的条件; 讨论超立方中是否存在完美匹配扩张成唯一一个哈密尔顿圈; 刻画 k 元 n 立方中不能扩张成哈密尔顿圈的完美匹配.

In 1993, Ruskey and Savage asked the following question: For n>1, does every matching in the n-dimensional hypercube extend to a hamiltonian cycle? Kreweras conjectured for n>1 that every perfect matching of the n-dimensional hypercube extends to a hamiltonian cycle. Fink confirmed the conjecture to be true. The k-ary n-cube is a generalization of the n-dimensional hypercube. We present a perfect matching which is not contained in any hamiltonian cycle in the k-ary n-cube. This shows that Kreweras' conjecture does not hold for the k-ary n-cube. In this project, we are going to investigate the hamiltonian cycles embedding problem in the hypercube with matchings and the hamiltonian cycles embedding problem in the k-ary n-cube with perfect matchings. In details, we will investigate the hamiltonian cycles embedding problem in the n-dimensional hypercube with such matchings whose size is a linear function of n or a exponential function of n, and characterize the conditions which are sufficient for these matchings to extend to a hamiltonian cycle in the hypercube; We discuss the perfect matching which is contained in exactly one hamiltonian cycle in the hypercube; We characterize the perfect matching which is not contained in any hamiltonian cycle in the k-ary n-cube.