On the inequality \(dk(G)\leq k(G)+1\) (Q2761055)

The competition graph (competition-common enemy graph) of an acyclic digraph \(D\) is the undirected graph \(G\) with \(V(G)=V(D)\) and with \(x,y\in V(G)\) being adjacent if and only if \((x,a)\), \((y,a)\) are arcs of \(D\) for some vertex \(a\) (\((x,a)\), \((y,a)\), \((b,x)\), \((b,y)\) are arcs of \(D\) for some vertices \(a,b\)). The smallest integer \(k\) such that a graph \(G\) together with \(k\) additional isolated vertices becomes a competition graph (a competition-common enemy graph) is called the competition number (the double competition number) of \(G\) and is denoted by \(k(G)\) (\(dk(G)\)). It is known that \(dk(G)\leq k(G)+1\) for any graph \(G\). In the paper (i) a sufficient condition is given under which \(dk(G)\leq k(G)\) (specifically, \(dk(G)\leq k(G)\) if \(G\) is triangle-free with \(k(G)\geq 2\)), (ii) an upper bound for \(dk(G)\) of a connected triangle-free graph \(G\) is given, and (iii) it is shown that \(k(G)=2\) and \(dk(G)=3\) for an infinite family of Harary graphs.