On The Inequality $dk(G)\le k(G)+1$

Abstract

Let $D$ be an acyclic digraph. The competition graph of $D$ has the same set of vertices as $D$ and an edge between vertices $u$ and $v$ if and only if there is a vertex $x$ in $D$ such that $(u,x)$ and $(v,x)$ are arcs of $D$. The competition-common enemy graph of $D$ has the same set of vertices as $D$ and an edge between vertices $u$ and $v$ if and only if there are vertices $w$ and $x$ in $D$ such that $(w,u),(w,v),(u,x)$, and $(v,x)$ are arcs of $D$. The competition number (respectively, double competition number) of a graph $G$, denoted by $k(G)$ (respectively, $dk(G)$), is the smallest number $k$ such that $G$ together with $k$ isolated vertices is a competition graph (respectively, competition-common enemy graph) of an acyclic digraph.

It is known that $dk(G)\le k(G)+1$ for any graph $G$. In this paper, we give a sufficient condition under which a graph $G$ satisfies $dk(G)\le k(G)$ and show that any connected triangle-free graph $G$ with $k(G)\ge 2$ satisfies that condition. We also give an upper bound for the double competition number of a connected triangle-free graph. Finally, we find an infinite family of graphs each member $G$ of which satisfies $k(G)=2$ and $dk(G)>k(G)$.