Hypothesis-checker: Source code of the checker of induction assumption for an article by P. Gregor, T. Novotný, R. Škrekovski: ”Extending perfect matchings to Gray codes with prescribed ends”. A binary (cyclic) Gray code is a (cyclic) ordering of all binary strings of the same length such that any two consecutive strings differ in a single bit. This corresponds to a Hamiltonian path (cycle) in the hypercube. Fink showed that every perfect matching in the n-dimensional hypercube Qn can be extended to a Hamiltonian cycle, confirming a conjecture of Kreweras. In this paper, we study the “path version” of this problem. Namely, we characterize when a perfect matching in Qn extends to a Hamiltonian path between two prescribed vertices of opposite parity. Furthermore, we characterize when a perfect matching in Qn with two faulty vertices extends to a Hamiltonian cycle. In both cases we show that for all dimensions n≥5 the only forbidden configurations are so-called half-layers, which are certain natural obstacles. These results thus extend Kreweras’ conjecture with an additional edge, or with two faulty vertices. The proof for the case n=5 is computer-assisted.
Keywords for this software
References in zbMATH (referenced in 2 articles , 1 standard article )
Showing results 1 to 2 of 2.
- Gregor, Petr; Novotný, Tomáš; Škrekovski, Riste: Extending perfect matchings to Gray codes with prescribed ends (2018)
- Fink, Jiří; Dvořák, Tomáš; Gregor, Petr; Novotný, Tomáš: Towards a problem of Ruskey and Savage on matching extendability (2017)