Inhalt des Dokuments
Preprint 669-2000
Combinatorial Optimization & Graph Algorithms group (COGA-Preprints)- Title
- A Note on a Question of C. D. Savage
- Author
- Classification
-
MSC: primary: 05C45 Eulerian and Hamiltonian graphs secondary: 05C20 Directed graphs , tournaments 05C30 Enumeration of graphs and maps 06A07 Combinatorics of partially ordered sets - Keywords
-
Hamilton path; acyclic orientation; poset; linear extension; adjacent transposition
- Abstract
-
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.
- Source
- Download as [ps.gz]
Zusatzinformationen / Extras
Direktzugang
Schnellnavigation zur Seite über Nummerneingabe