超立方中匹配的哈密尔顿圈扩张和2-因子扩张及其相关问题的研究

Ruskey和Savage在1993年提出了如下问题：超立方中每一个匹配能否扩张成一个哈密尔顿圈？Kreweras猜想：超立方中每一个完美匹配可以扩张成一个哈密尔顿圈。Fink证明了上述猜想是正确的。Gregor等人证明了超立方中每一个恰好有两个未覆盖点的匹配可扩张成一个哈密尔顿圈。Dvorak等人证明了超立方中每一个大小不超过n^2/16+n/4的匹配可扩张成一个哈密尔顿圈。本项目将研究超立方中有4个或多个点未被覆盖的这一类极大匹配和平方阶匹配的哈密尔顿圈扩张性质。Vandenbussche和West提出了一个弱化的问题。他们猜想：超立方中每一个匹配可扩张成一个2-因子。Fink证明了这个猜想是正确的。受此启发，本项目还将研究超立方中匹配能否扩张成只含有少量圈(4个圈，2个圈，或1个圈)的2-因子。平衡超立方是超立方的一种变体，进一步地本项目还将研究平衡超立方中匹配的哈密尔顿圈扩张性质。

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. Gregor proved that every matching of Qn which covers all but two vertices of Qn extends to a hamiltonian cycle. Dvorak and Fink proved that every matching in Qn of size at most n^2/16+n/4 extends to a hamiltonian cycle. Even though a positive answer is known in some special cases, the problem still remains open in general. In this project, we are going to discuss the problem of the maximal matchings with four or more points uncovered extend to hamiltonian cycles and the problem of matchings of quadratic size extend to hamiltonian cycles. Vandenbussche and West conjectured that every matching in the hypercube extends to a 2-factor, which is a weaker variant of the Ruskey-Savage problem. Fink proved this conjecture to be true. In this project, we are going to investigate how to significantly reduce the number of cycles in a 2-factor, ideally to a single one. In addition, the balanced hypercube is a variant of the hypercube network. In this project, we are going to discuss the problem of matchings extend to hamiltonian cycles in balanced hypercubes.