A Note on a Question of C. D. Savage
| dc.contributor.author | Naatz, Michael | |
| dc.date.accessioned | 2022-05-11T12:11:39Z | |
| dc.date.available | 2022-05-11T12:11:39Z | |
| dc.date.issued | 2000 | |
| dc.description.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. | en |
| dc.identifier.issn | 2197-8085 | |
| dc.identifier.uri | https://depositonce.tu-berlin.de/handle/11303/16892 | |
| dc.identifier.uri | http://dx.doi.org/10.14279/depositonce-15670 | |
| dc.language.iso | en | |
| dc.rights.uri | http://rightsstatements.org/vocab/InC/1.0/ | |
| dc.subject.ddc | 510 Mathematik | en |
| dc.subject.other | Hamilton path | en |
| dc.subject.other | acyclic orientation | en |
| dc.subject.other | poset | en |
| dc.subject.other | linear extension | en |
| dc.subject.other | adjacent transposition | en |
| dc.title | A Note on a Question of C. D. Savage | en |
| dc.type | Research Paper | en |
| dc.type.version | submittedVersion | en |
| tub.accessrights.dnb | free | |
| tub.affiliation | Fak. 2 Mathematik und Naturwissenschaften::Inst. Mathematik | de |
| tub.affiliation.faculty | Fak. 2 Mathematik und Naturwissenschaften | de |
| tub.affiliation.institute | Inst. Mathematik | de |
| tub.publisher.universityorinstitution | Technische Universität Berlin | en |
| tub.series.issuenumber | 2000, 669 | en |
| tub.series.name | Preprint-Reihe des Instituts für Mathematik, Technische Universität Berlin | en |
| tub.subject.msc2000 | 05C45 Eulerian and Hamiltonian graphs | en |
| tub.subject.msc2000 | 05C20 Directed graphs, tournaments | en |
| tub.subject.msc2000 | 05C30 Enumeration of graphs and maps | en |
| tub.subject.msc2000 | 06A07 Combinatorics of partially ordered sets | en |
Files
Original bundle
1 - 1 of 1