id: 06046354
dt: j
an: 06046354
au: Kim, Suh-Ryung; Lee, Jung Yeun; Park, Boram; Sano, Yoshio
ti: The competition number of a graph and the dimension of its hole space.
so: Appl. Math. Lett. 25, No. 3, 638-642 (2012).
py: 2012
pu: Elsevier Science Ltd. (Pergamon), Oxford
la: EN
cc:
ut: competition graph; competition number; cycle space; hole; hole space
ci:
li: doi:10.1016/j.aml.2011.10.003
ab: Summary: 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 to characterize a graph by its competition number. Recently, the
relationship between the competition number and the number of holes of
a graph has been studied. A hole of a graph is a cycle of length at
least 4 as an induced subgraph. In this paper, we conjecture that the
dimension of the hole space of a graph is not smaller than the
competition number of the graph. We verify this conjecture for various
kinds of graphs and show that our conjectured inequality is indeed an
equality for connected triangle-free graphs.
rv: