The prism of the acyclic orientation graph is Hamiltonian (Q1346739)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | The prism of the acyclic orientation graph is Hamiltonian |
scientific article |
Statements
The prism of the acyclic orientation graph is Hamiltonian (English)
0 references
6 April 1995
0 references
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.
0 references
acyclic orientation
0 references
prism
0 references
Hamiltonian
0 references