| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 6423897 | Electronic Notes in Discrete Mathematics | 2011 | 6 Pages |
Abstract
The linear extension diameter of a finite poset P is the diameter of the graph on all linear extensions of P as vertices, two of them being adjacent whenever they differ in exactly one (adjacent) transposition. Recently, Felsner and Massow determined the linear extension diameter of the Boolean lattice B, and they posed a question of determining the linear extension diameter of a subposet of B induced by two levels. We solve the case of the 1st and kth level. The diametral pairs are obtained from minimal vertex covers of so called dependency graphs, a new concept which may be useful also for the general case.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
JiÅÃ Fink, Petr Gregor,