Publication at Faculty of Mathematics and Physics |
2007
Abstract
Kreweras' conjecture asserts that every perfect matching of the hypercube Qd can be extended to a Hamiltonian cycle. We proved this conjecture but here we present a simplified proof.
The matching graph M(G) of a graph G has a vertex set of all perfect matchings of G, with two vertices being adjacent whenever the union of the corresponding perfect matchings forms a Hamiltonian cycle. We prove that the matching graph of the d-dimensional hypercube is bipartite for d