Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
418803 | Discrete Applied Mathematics | 2009 | 5 Pages |
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
Bo-Jr Li, Gerard J. Chang,