Minimizing the jump number for partially ordered sets: A graph-theoretic approach (Q1057887): Difference between revisions

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, another digraph can be assigned, which is the root digraph of the Hasse diagram of P. Using this representation it is shown that the jump number of an N-free poset is equal to the cyclomatic number of its root digraph and can be found by an algorithm which tests if a given poset is N-free.