Competitively tight graphs

Abstract

The competition graph of a digraph $D$ is a (simple undirected) graph which has the same vertex set as $D$ and has an edge between two distinct vertices $x$ and $y$ if and only if there exists a vertex $v$ in $D$ such that $(x,v)$ and $(y,v)$ are arcs of $D$. For any graph $G$, $G$ together with sufficiently many isolated vertices is the competition graph of some acyclic digraph. The competition number $k(G)$ of a graph $G$ is the smallest number of such isolated vertices. Computing the competition number of a graph is an NP-hard problem in general and has been one of the important research problems in the study of competition graphs. Opsut [1982] showed that the competition number of a graph $G$ is related to the edge clique cover number ${\theta }_E(G)$ of the graph $G$ via ${\theta }_E(G)-|V(G)|+2\le k(G)\le {\theta }_E(G)$. We first show that for any positive integer $m$ satisfying $2\le m\le |V(G)|$, there exists a graph $G$ with $k(G)={\theta }_E(G)-|V(G)|+m$ and characterize a graph $G$ satisfying $k(G)={\theta }_E(G)$. We then focus on what we call \emph{competitively tight graphs} $G$ which satisfy the lower bound, i.e., $k(G)={\theta }_E(G)-|V(G)|+2$. We completely characterize the competitively tight graphs having at most two triangles. In addition, we provide a new upper bound for the competition number of a graph from which we derive a sufficient condition and a necessary condition for a graph to be competitively tight.

10 pages, 2 figures

References in corpus (3)

• The competition number of a graph and the dimension of its hole space
• A generalization of Opsut's lower bounds for the competition number of a graph
• Competition Numbers, Quasi-Line Graphs and Holes