On a long cycle in the graph of all linear extensions of a poset consisting of two disjoint chains

DOI10.1016/0012-365X(94)90401-4MaRDI QIDQ1331990zbMATH OpenOpenAlexFDO

Authors Grzegorz Stachowiak

Publication date 26 January 1995

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0012-365x(94)90401-4

zbMATH Keywords

chainsgraphHamilton cycleHamilton pathlinear extensionslong cycleposet

Mathematics Subject Classification ID

Paths and cycles (05C38) Eulerian and Hamiltonian graphs (05C45) Ordered sets (06A99)

Review text

Given \({\mathcal L}(P)\) the collection of linear extensions of a poset \(P\), then \(G(P)\) denotes the graph obtained by taking \(L_ 1\), \(L_ 2\) to be adjacent iff \(L_ 1\) and \(L_ 2\) differ from each other via a single transposition of two adjacent elements. If \(G(P)\) has a Hamilton path, then there exists a simple algorithm for generating all linear extensions of \(P\). Previous results referring to posets which are sums of two chains (here called parallel of two chains denoted \(0^ n\) and \(1^ m\) of lengths \(n\) and \(m\) respectively) are extended to obtain Theorem 3, i.e., if in \(G(0^ n + 1^ m)\) those vertices corresponding to \(0^ n \oplus 1^ m\) and \(1^ m \oplus 0^ n\) are removed \((m,n \geq 3)\), then the resulting graph has a Hamilton cycle.

Recommendations

• Generating the Linear Extensions of Certain Posets by Transpositions
• Hamilton Paths in Graphs of Linear Extensions for Unions of Posets
• scientific article; zbMATH DE number 4106894
• The Graph of Linear Extensions Revisited

Cites work

• Adjacent interchange generation of combinations
• Generating linear extensions of posets by transpositions
• Gray codes with restricted density
• Hamilton Paths in Graphs of Linear Extensions for Unions of Posets
• Solution of some multi-dimensional lattice path parity difference recurrence relations
• Some Hamilton Paths and a Minimal Change Algorithm

Cited in

(7)

• On the existence of Hamiltonian paths in the cover graph of M(n)
• scientific article; zbMATH DE number 4106894 (Why is no real title available?)
• Generating the Linear Extensions of Certain Posets by Transpositions
• Hamilton Paths in Graphs of Linear Extensions for Unions of Posets
• The Graph of Linear Extensions Revisited
• First-Fit is linear on posets excluding two long incomparable chains
• Linear extension majority cycles in height-1 orders

This page was built for publication: On a long cycle in the graph of all linear extensions of a poset consisting of two disjoint chains

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1331990)