The prism of the acyclic orientation graph is Hamiltonian
The electronic journal of combinatorics, Tome 2 (1995)
Every connected simple graph $G$ has an acyclic orientation. Define a graph ${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 ${AO}(G)$ is connected but not necessarily Hamiltonian. However, Squire proved that the square ${AO}(G)^2$ is Hamiltonian. We prove the slightly stronger result that the prism ${AO}(G) \times e$ is Hamiltonian. If $G$ is a mixed graph (some edges directed, but not necessarily all), then ${AO}(G)$ can be defined as before. The graph ${AO}(G)$ is again connected but we give examples showing that the prism is not necessarily Hamiltonian.
@article{10_37236_1199,
author = {Gara Pruesse and Frank Ruskey},
title = {The prism of the acyclic orientation graph is {Hamiltonian}},
journal = {The electronic journal of combinatorics},
year = {1995},
volume = {2},
doi = {10.37236/1199},
zbl = {0814.05055},
url = {http://geodesic.mathdoc.fr/articles/10.37236/1199/}
}
Gara Pruesse; Frank Ruskey. The prism of the acyclic orientation graph is Hamiltonian. The electronic journal of combinatorics, Tome 2 (1995). doi: 10.37236/1199
Cité par Sources :