## 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.

Original language | English (US) |
---|---|

Pages (from-to) | 97-113 |

Number of pages | 17 |

Journal | Ars Combinatoria |

Volume | 50 |

State | Published - Dec 1 1998 |

## All Science Journal Classification (ASJC) codes

- Mathematics(all)