The elimination procedure for the competition number

Suh Ryung Kim, Fred S. Roberts

Research output: Contribution to journalArticle

2 Scopus citations


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.

Original languageEnglish (US)
Pages (from-to)97-113
Number of pages17
JournalArs Combinatoria
StatePublished - Dec 1 1998

All Science Journal Classification (ASJC) codes

  • Mathematics(all)

Fingerprint Dive into the research topics of 'The elimination procedure for the competition number'. Together they form a unique fingerprint.

Cite this