direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Logo der TU Berlin

Inhalt des Dokuments

Preprint 669-2000

Combinatorial Optimization & Graph Algorithms group (COGA-Preprints)

A Note on a Question of C. D. Savage
primary: 05C45 Eulerian and Hamiltonian graphs
secondary: 05C20 Directed graphs , tournaments
05C30 Enumeration of graphs and maps
06A07 Combinatorics of partially ordered sets
Hamilton path; acyclic orientation; poset; linear extension; adjacent transposition
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.
Download as [ps.gz]
Title: Source

Zusatzinformationen / Extras


Schnellnavigation zur Seite über Nummerneingabe