Affordable Access

Publisher Website

Adamant digraphs

Authors
Journal
Discrete Mathematics
0012-365X
Publisher
Elsevier
Publication Date
Volume
69
Issue
3
Identifiers
DOI: 10.1016/0012-365x(88)90054-4
Disciplines
  • Computer Science

Abstract

Abstract In this paper we introduce the class of adamant digraphs. These are the digraphs with the property that for any two vertices x and y, the set of successors of x and the set of successors of y are either disjoint or (inclusionwise) comparable. Those adamant digraphs whose inverse digraph is also adamant are called inflexible. This subclass includes many previously known classes, e.g. minimal series-parallel digraphs and Ferrers digraphs. For both adamant and inflexible digraphs we give alternative characterizations and linear-time recognition algorithms. The special case of symmetric adamant digraphs is investigated.

There are no comments yet on this publication. Be the first to share your thoughts.

Statistics

Seen <100 times
0 Comments

More articles like this

X k-Digraphs

on Journal of Combinatorial Theor... Jan 01, 1981
More articles like this..