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

In this paper, we prove that if a graph GG is diamond-free, then the competition number of GG is bounded above by 2+12∑v∈Vh(G)(θV(NG(v))−2) where Vh(G)Vh(G) is the set of nonsimplicial vertices of GG. 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.