The Elimination, Procedure for the Competition Number

Abstract

If $D$ is an acyclic digraph, its competition graph is an undirected graph with the same vertex set and an edge between vertices $x$ and $y$ if there is a vertex $a$ so that $(x,a)$ and $(y,a)$ are both arcs of $D$. If $G$ is any graph, $G$ together with sufficiently many isolated vertices is a competition graph, and the competition number of $G$ is the smallest number of such isolated vertices. Roberts $[1978]$ gives an elimination procedure for estimating the competition number and Opsut $[1982]$ showed that this procedure could overestimate. In this paper, we modify that elimination procedure and then show that for a large class of graphs it calculates the competition number exactly.