The Competition Graphs of Interval Digraphs
Larry J. Langley, J. Richard Lundgren, Sarah K. Merz · 1995
. Given a digraph D, we construct the competition graph of D, C(D), on the same vertex set as D with x and y adjacent in C(D) if and only if there exists a vertex z such that x and y both have arcs to z in D. A digraph is an interval digraph if and only if two intervals S(x) and T (x) on the real line can be assigned to vertex x such that (x; y) 2 A(D) if and only if S(x) " T (y) 6= ;. In this paper we show that the competition graph of an interval digraph is an interval graph and that every interval graph is in fact the competition graph of some digraph. These results are then related to previous work on competition graphs. 1. Introduction. Given a digraph D, we construct the competition graph of D, C(D) on the same vertex set as D with x and y adjacent in C(D) if and only if there exists a vertex z such that x and y both have arcs to z in D. Though introduced by Cohen [1] in the study of food webs, competition graphs have been applied to other models such as communication networks b...