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  gives an elimination procedure for estimating the competition number and Opsut  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.
|Original language||English (US)|
|Number of pages||17|
|State||Published - Dec 1 1998|
All Science Journal Classification (ASJC) codes