The prism of the acyclic orientation graph is Hamiltonian (Q1346739)

Summary: Every connected simple graph \(G\) has an acyclic orientation. Define a graph \(\text{AO}(G)\) whose vertices are the acyclic orientations of \(G\) and whose edges join orientations that differ by reversing the direction of a single edge. It was known previously that \(\text{AO}(G)\) is connected but not necessarily Hamiltonian. However, Squire proved that the square \(\text{AO}(G)^ 2\) is Hamiltonian. We prove the slightly stronger result that the prism \(\text{AO}(G)\times e\) is Hamiltonian. If \(G\) is a mixed graph (some edges directed, but no necessarily all), then \(\text{AO}(G)\) can be defined as before. The graph \(\text{AO}(G)\) is again connected but we give examples showing that the prism is not necessarily Hamiltonian.