Competition Graphs

The competition graph C(D) of a digraph D=(V,A) has the same vertex set as D, and two distinct vertices x, y are adjacent in C(D) if there is some vertex zV (possibly x or y) such that xz,yzA. In other words, C(D) is the intersection graph of the family of all out-neighborhoods of the vertices in D.

What families occur as such families of all out-neighborhoods of digraphs? Obviously exactly those hypergraphs that have as many vertices as edges. Thinking in terms of row-intersection graphs of matrices, competition graphs are therefore exactly the row-intersection graphs of 0-1 square matrices, and therefore a superclass of the class of intersection graphs of self-dual hypergraphs.

Since this property to have exactly as many edges as vertices is self-dual, dualization yields immediately the following characterization of competition graphs:

[DB83]: A graph G=(V,E) is the competition graph of some digraph if and only if G has some covering of the its edges by |V| complete subgraphs.

Note that the family F of all in-neighborhoods of a digraph is the dual of the family of all its out-neighborhoods. The intersection graph of this family F is the resource graph of the digraph.

A lot of the work that has been done in this field is surveyed in [MM99] or in [L89].

Back to the start page for intersection graphs