Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
418710 | Discrete Applied Mathematics | 2010 | 4 Pages |
Abstract
A hole of a graph is an induced cycle of length at least 4. Kim (2005) [2] conjectured that the competition number k(G)k(G) is bounded by h(G)+1h(G)+1 for any graph GG, where h(G)h(G) is the number of holes of GG. In Lee et al. [3], it is proved that the conjecture is true for a graph whose holes are mutually edge-disjoint. In Li et al. (2009) [4], it is proved that the conjecture is true for a graph, all of whose holes are independent. In this paper, we prove that Kim’s conjecture is true for a graph GG satisfying the following condition: for each hole CC of GG, there exists an edge which is contained only in CC among all induced cycles of GG.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Akira Kamibeppu,