Name
Abstract | ||
|---|---|---|
Kreweras' conjecture [G. Kreweras: Matchings and Hamiltonian cycles on hypercubes, Bull. Inst. Combin. Appl. 16 (1996) 87–91] asserts that every perfect matching of the hypercube Q d can be extended to a Hamiltonian cycle. We [J. Fink: Perfect Matchings Extend to Hamilton Cycles in Hypercubes, to appear in J. Comb. Theory, Series B] 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 M ( Q d ) of the d -dimensional hypercube is bipartite for d ≥ 2 and connected for d ≥ 4 . This proves another Kreweras' conjecture [G. Kreweras: Matchings and Hamiltonian cycles on hypercubes, Bull. Inst. Combin. Appl. 16 (1996) 87–91] that the graph M d is connected, where M d is obtained from M ( Q d ) by contracting every pair of vertices of M ( Q d ) whose corresponding perfect matchings are isomorphic. |
Year | DOI | Venue |
|---|---|---|
2007 | 10.1016/j.endm.2007.07.059 | Electronic Notes in Discrete Mathematics |
Keywords | Field | DocType |
hypercube,hamiltonian cycle,perfect matching,complete bipartite graph | Complete graph,Discrete mathematics,Combinatorics,Hypercube graph,Hamiltonian path,Folded cube graph,Graph factorization,Bipartite graph,Factor-critical graph,Mathematics,Perfect graph theorem | Journal |
Volume | Issue | ISSN |
29 | 7 | Electronic Notes in Discrete Mathematics |
Citations | PageRank | References |
5 | 0.47 | 8 |
Authors | ||
1 | ||