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

    Identifiers