2003-42: The Elimination Procedure for the Competition Number is Not Optimal

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