Natalie Behague

Semi-perfect 1-Factorizations of the Hypercube

A 1-factorization of a graph H is a partition of the edges of H into disjoint perfect matchings {M_1 , M_2 , . . . , M_n}, also known as 1-factors. A 1-factorization M = {M_1 , M_2 , . . . , M_n} of a graph G is called perfect if the union of any pair of distinct 1-factors M_i , M_j is a Hamilton cycle. The existence or non-existence of perfect 1-factorizations has been studied for various families of graphs. Perhaps the most famous open problem in the area is Kotzig’s conjecture, which states that the complete graph K_2n has a perfect 1-factorization. In this talk we shall focus on another well-studied family of graphs: the hypercubes Q_d in d dimensions. There is no perfect 1-factorization of Q_d for d > 2. As a result, we need to consider a weaker concept.

A 1-factorization M is called k-semi-perfect if the union of any pair of 1-factors M_i , M_j with 1 ≤ i ≤ k and k + 1 ≤ j ≤ n is a Hamilton cycle. It was proved that there is a 1-semi-perfect 1-factorization of Q_d for every integer d ≥ 2 by Gochev and Gotchev, Královič and Královič, and Chitra and Muthusamy, in answer to a conjecture of Craft. My main result is a proof that there is a k-semi-perfect 1-factorization of Q_d for all k and all d, except for one possible exception when k = 3 and d = 6. I will sketch the proof and explain why this is, in some sense, best possible. I will conclude with some questions concerning other generalisations of perfect 1-factorizations.