Interval digraphs: An analogue of interval graphs

✍ Scribed by S. Das; M. Sen; A. B. Roy; D. B. West

• Publisher: John Wiley and Sons
• Year: 1989
• Tongue: English
• Weight: 728 KB
• Volume: 13
• Category: Article
• ISSN: 0364-9024
• DOI: 10.1002/jgt.3190130206

✦ Synopsis

Intersection digraphs analogous to undirected intersection graphs are introduced. Each vertex is assigned an ordered pair of sets, with a directed edge uu in the intersection digraph when the "source set" of u intersects the "terminal set" of u. 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 o f ' Ferrers digraphs whose union is a complete digraph.