Loading...
Please wait, while we are loading the content...
Similar Documents
The Graph Of Linear Extensions Revisited (0)
| Content Provider | CiteSeerX |
|---|---|
| Author | Naatz, Michael |
| Abstract | The graph of linear extensions G(P ) of a poset P has as vertices the linear extensions of P , and two vertices are adjacent if they differ only by an adjacent transposition. This graph has so far been investigated mainly with respect to Hamilton paths and intrinsic geodesic convexity. Especially the work on the latter topic showed how the graph-theoretic properties of G(P ) reflect the order-theoretic structure of P . The aim of this paper is to study the graph G(P ) with respect to topics from classical graph theory, e.g., connectivity, cycle space, isometric embeddings, and nd order-theoretic interpretations of these notions. The main theorems in this paper are the equality of the connectivity of G(P ) and the jump number of P , the existence of a certain generating system for the cycle space and a relationship of P and its subposets obtained via an embedding of the graph of linear extensions. |
| File Format | |
| Volume Number | 13 |
| Journal | SIAM J. Disc. Math |
| Language | English |
| Access Restriction | Open |
| Subject Keyword | Linear Extension Cycle Space Hamilton Path Graph-theoretic Property Nd Order-theoretic Interpretation Classical Graph Theory Latter Topic Order-theoretic Structure Main Theorem Intrinsic Geodesic Convexity Adjacent Transposition Jump Number Certain Generating System Isometric Embeddings |
| Content Type | Text |
| Resource Type | Article |
