A note on a question of C. D. Savage (Q2706193)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: A note on a question of C. D. Savage |
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | A note on a question of C. D. Savage |
scientific article |
Statements
19 March 2001
0 references
Hamilton path
0 references
Hamilton cycle
0 references
acyclic orientation
0 references
poset
0 references
linear extension
0 references
adjacent transposition
0 references
A note on a question of C. D. Savage (English)
0 references
Consider a graph \(G\) and a fixed orientation of a subset \(E\) of the edge set of \(G\). Then consider a new bipartite graph whose vertices are all acyclic orientations which extend the orientation of \(E\). Two vertices in the new graph are neighbors, if their orientations disagree on precisely one edge. The author shows that such a graph need not have a Hamiltonian path even when the cardinalities of the two bipartite classes differ by only \(1\).
0 references
