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*) `X` *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.

- The postscript file is ??? bytes, the dvi file is ??? bytes.
- Appears in Electronic Journal of Combinatorics, paper R5.

Back to list of publications.