A generalization of Opsut's result on the competition numbers of line graphs

作者：Kim Suh Ryung; Lee Jung Yeun; Park Boram^*; Sano Yoshio

来源：Discrete Applied Mathematics, 2015, 181: 152-159.

DOI：10.1016/j.dam.2014.10.014

• Competition graph
• Competition number
• Edge clique cover
• Line graph
• Diamond-free graph
• Edge-buffered graph
• Quasi-line graph
• Opsut's conjecture

In this paper, we prove that if a graph G is diamond-free, then the competition number of G is bounded above by 2 +1/2 Sigma(v is an element of vh(G))(theta(V)(N-G(upsilon)) - 2) where V-h (G) is the set of nonsimplicial vertices of G. This result generalizes Opsut's result for line graphs. We also show that the upper bound holds for certain graphs which might have diamonds. As a matter of fact, we go further to a conjecture that the above upper bound holds for the competition number of any graph, which leads to a natural generalization of Opsut's conjecture.

• 出版日期2015-1-30