## DIMACS TR: 2003-42

##
The Elimination Procedure for the Competition Number is Not Optimal

### Author: Stephen Hartke

**
ABSTRACT
**
Given an acyclic digraph D, the competition graph C(D) is defined to be the
undirected graph with V(D) as its vertex set and where vertices x and y are
adjacent if there exists another vertex z such that the arcs (x,z) and (y,z)
are both present in G. The competition number k(G) for an undirected graph G
is the least number r such that there exists an acyclic digraph F on |V(G)|+r
vertices where C(F) is G along with r isolated vertices. Kim and Roberts]
introduced an elimination procedure for the competition number, and asked
whether the procedure calculated the competition number for all graphs. We
answer this question in the negative by demonstrating a graph where the
elimination procedure does not calculate the competition number. This graph
also provides a negative answer to a similar question about the related
elimination procedure for the phylogeny number.

Paper available at ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2003/2003-42.ps.gz

DIMACS Home Page