The Elimination, Procedure for the Competition Number

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.