ISSN:
1572-9273
Keywords:
06A10
;
05C20
;
68C25
;
Partial order
;
linear extension
;
jump number
;
line digraph
;
cyclomatic number
;
spanning branching
;
Eulerian digraph
Source:
Springer Online Journal Archives 1860-2000
Topics:
Mathematics
Notes:
Abstract The purpose of this paper is to present a graph-theoretic approach to the jump number problem for N-free posets which is based on the observation that the Hasse diagram of an N-free poset is a line digraph. Therefore, to every N-free poset P we can assign another digraph which is the root digraph of the Hasse diagram of P. Using this representation we show that the jump number of an N-free poset is equal to the cyclomatic number of its root digraph and can be found (without producing any linear extension) by an algorithm which tests if a given poset is N-free. Moreover, we demonstrate that there exists a correspondence between optimal linear extensions of an N-free poset and spanning branchings of its root digraph. We provide also another proof of the fact that optimal linear extensions of N-free posets are exactly greedy linear extensions. In conclusion, we discuss some possible generalizations of these results to arbitrary posets.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF00396269
Permalink
