| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 420795 | Discrete Applied Mathematics | 2006 | 7 Pages |
Given an acyclic digraph D , the competition graph C(D)C(D) is defined to be the undirected graph with V(D)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)(x,z) and (y,z)(y,z) are both present in D . The competition number k(G)k(G) for an undirected graph G is the least number r such that there exists an acyclic digraph F on |V(G)|+r|V(G)|+r vertices where C(F)C(F) is G along with r isolated vertices. Kim and Roberts [The Elimination Procedure for the Competition Number, Ars Combin. 50 (1998) 97–113] 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 introduced by the current author in [S.G. Hartke, The Elimination Procedure for the Phylogeny Number, Ars Combin. 75 (2005) 297–311].
