Article ID Journal Published Year Pages File Type
418803 Discrete Applied Mathematics 2009 5 Pages PDF
Abstract

Given an acyclic digraph DD, the competition graph C(D)C(D) of DD is the graph with the same vertex set as DD where two distinct vertices xx and yy are adjacent in C(D)C(D) if and only if there is a vertex vv in DD such that (x,v)(x,v) and (y,v)(y,v) are arcs of DD. The competition number κ(G)κ(G) of a graph GG is the least number of isolated vertices that must be added to GG to form a competition graph. The purpose of this paper is to prove that the competition number of a graph with exactly hh holes, all of which are independent, is at most h+1h+1. This generalizes the result for h=0h=0 given by Roberts, and the result for h=1h=1 given by Cho and Kim.

Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
, ,