Premium
Interval digraphs: An analogue of interval graphs
Author(s) -
Das S.,
Sen M.,
Roy A. B.,
West D. B.
Publication year - 1989
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.3190130206
Subject(s) - digraph , combinatorics , mathematics , vertex (graph theory) , intersection (aeronautics) , discrete mathematics , adjacency matrix , interval (graph theory) , graph , engineering , aerospace engineering
Abstract Intersection digraphs analogous to undirected intersection graphs are introduced. Each vertex is assigned an ordered pair of sets, with a directed edge uv in the intersection digraph when the “source set” of u intersects the “terminal set” of v. Every n ‐vertex digraph is an intersection digraph of ordered pairs of subsets of an n ‐set, but not every digraph is an intersection digraph of convex sets in the plane. Interval digraphs are those having representations where all sets are intervals on the real line. Interval digraphs are characterized in terms of the consecutive ones property of certain matrices, in terms of the adjacency matrix and in terms of Ferrers digraphs. In particular, they are intersections of pairs of Ferrers digraphs whose union is a complete digraph.