Minimizing the jump number for partially ordered sets: A graph-theoretic approach
type: Item
instance of: scholarly article
title: Minimizing the jump number for partially ordered sets: A graph-theoretic approach
zbMATH Open document ID: 0564.06001
DOI: 10.1007/BF00396269
published in: Order
publication date: 1984-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 06A06
Mathematics Subject Classification ID: 05A19
Mathematics Subject Classification ID: 05C20
Mathematics Subject Classification ID: 05C30
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 06B15
zbMATH DE Number: 3898946
zbMATH Keywords: jump number problem
zbMATH Keywords: N-free posets
zbMATH Keywords: Hasse diagram
zbMATH Keywords: line digraph
zbMATH Keywords: root digraph
zbMATH Keywords: representation
zbMATH Keywords: cyclomatic number
author: Maciej M. Sysło
reviewed by: Philippe Vincke
MaRDI profile type: Publication
cites work: The Jump Number of Dags and Posets: An Introduction
cites work: Q4200070
cites work: Q5572939
cites work: Q3872508
cites work: A labeling algorithm to recognize a line digraph and output its root graph
cites work: Optimal constructions of reversible digraphs
full work available at URL: https://doi.org/10.1007/bf00396269
OpenAlex ID: W2082183871
description: scientific article; zbMATH DE number 3898946