Mathematics – Combinatorics
Scientific paper
2011-12-28
Mathematics
Combinatorics
9 pages, 2 figures
Scientific paper
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 $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 $G$ is the smallest number of such isolated vertices. In general, it is hard to compute the competition number $k(G)$ for a graph $G$ and it has been one of the important research problems in the study of competition graphs. Opsut~[1982] suggested that the edge clique cover number $\theta_E(G)$ should be closely related to $k(G)$ by showing $\theta_E(G)-|V(G)|+2 \leq k(G) \leq \theta_E(G)$. In this note, we study on these inequalities. We first show that for any positive integer $m$ satisfying $2 \leq m \leq |V(G)|$, there is a graph $G$ satisfying $k(G)=\theta_E(G)-|V(G)|+m$ and characterize a graph $G$ satisfying $k(G)=\theta_E(G)$. Then we mainly focus on a so-called competitively tight graph $G$ satisfying 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 a competition number of a graph from which we derive a sufficient condition and a necessary condition for a graph to be competitively tight.
Kim Suh-Ryung
Lee Jung Yeun
Park Boram
Sano Yoshio
No associations
LandOfFree
Competitively tight graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Competitively tight graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Competitively tight graphs will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-728242