A note on a question of C. D. Savage
type: Item
instance of: scholarly article
zbMATH Open document ID: 0969.05040
DOI: 10.1137/S0895480100369195
author: Michael Naatz
published in: SIAM Journal on Discrete Mathematics
publication date: 2001-03-19T00:00:00Z
Mathematics Subject Classification ID: 05C45
Mathematics Subject Classification ID: 05C20
Mathematics Subject Classification ID: 05C30
Mathematics Subject Classification ID: 06A07
zbMATH DE Number: 1578825
zbMATH Keywords: Hamilton path
zbMATH Keywords: Hamilton cycle
zbMATH Keywords: acyclic orientation
zbMATH Keywords: poset
zbMATH Keywords: linear extension
zbMATH Keywords: adjacent transposition
MaRDI profile type: Publication
title: A note on a question of C. D. Savage
review text: 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\).
reviewed by: Carsten Thomassen
description: scientific article