Loading…
A Note on a Question of C. D. Savage
Naatz, Michael
Preprint-Reihe des Instituts für Mathematik, Technische Universität Berlin
Given a graph G and an orientation~σ of some of its edges, consider the graph AOσ(G) which is defined as follows: The vertices are the acyclic orientations of G which agree with~σ, and two of these are adjacent if they differ only by the reversal of a single edge. AOσ(G) is easily seen to be bipartite. The purpose of this note is to show that it need not contain a Hamilton path even if both partite sets have the same cardinality. This answers a question of Carla D. Savage (SIAM Rev. 39(4):605-629,1997) and sheds new light onto two well-known open questions in the field of combinatorial Gray codes.
