On a long cycle in the graph of all linear extensions of a poset consisting of two disjoint chains (Q1331990)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On a long cycle in the graph of all linear extensions of a poset consisting of two disjoint chains |
scientific article |
Statements
On a long cycle in the graph of all linear extensions of a poset consisting of two disjoint chains (English)
0 references
26 January 1995
0 references
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.
0 references
long cycle
0 references
linear extensions
0 references
poset
0 references
graph
0 references
Hamilton path
0 references
chains
0 references
Hamilton cycle
0 references