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

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.

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

Ruskey和Savage在1993年提出了如下问题：当n>1时，n维超立方的每一个匹配能否扩张成一个哈密尔顿圈？Kreweras猜想：当n>1时，n维超立方的每一个完美匹配可以扩张成一个哈密尔顿圈。Fink证实了Kreweras的猜想的正确性。项目负责人在与张和平教授的合作下，从小匹配出发，用归纳和构造的方法证实了n维超立方中每一个大小不超过3n-10的匹配都可扩张成一个哈密尔顿圈。但是对其它大部分的匹配，此问题还没有得到一个完整的解决。k元n立方是超立方的一种推广，但是我们在研究的过程中发现，k元n立方的完美匹配不一定能扩张成哈密尔顿圈，这不同于超立方中完美匹配均可扩的结果。本项目主要研究超立方中匹配的哈密尔顿圈扩张性质和k元n立方中完美匹配的哈密尔顿圈扩张性质。本项目执行以来，已按计划取得了多项进展，具体内容如下：(1) 讨论了5维超立方中匹配扩张成哈密尔顿圈的问题，证明了5维超立方中的每一个匹配均可扩张成一个哈密尔顿圈。此结论为进一步探讨一般的问题打下了基础。(2) 通过对已知的研究成果的分析总结我们发现“超立方中每一个完美匹配可以扩张成一个哈密尔顿圈”这一性质相当美妙。那么一个自然的问题是：n维超立方中的每一个完美匹配能否扩张成多个哈密尔顿圈？我们运用递归构造的方法证明了当n>3时，n维超立方中的每一个完美匹配至少可扩张成2^{2^{n-4}}个不同的哈密尔顿圈。(3) k元n立方（其中k为偶数）的完美匹配不一定能扩张成哈密尔顿圈，所以一个自然的问题是，k元n立方中的哪些完美匹配可以扩张成哈密尔顿圈？关于此问题，我们得到了如下结果：k元n立方中的每一个由同维边构成的完美匹配可以扩张成一个哈密尔顿圈。(4) 容错性是衡量网络稳定性的一项重要指标。通常情形下，我们希望当网络中出现部分故障时仍能保证信息数据的正常传输，这就要求网络具有一定的容错能力。任意给定超立方中的一些故障边，故障超立方中是否仍然存在无故障哈密尔顿路连接任意两个不同颜色的点？（注：超立方是二部图。）关于此问题，我们得到了如下结果：对n≥6，令F是n维超立方Qn中的一个故障边集满足|F|≤3n-11。如果Qn-F中每一个点的度都至少为2且Qn-F中至多只有一个2度点，则Qn-F中存在哈密尔顿路连接任意两个不同颜色的点。