Mathematics – Combinatorics
Scientific paper
2009-09-29
Applied Mathematics Letters 24 (2011) 1331-1335
Mathematics
Combinatorics
6 pages, 1 figure
Scientific paper
10.1016/j.aml.2011.03.003
The competition number k(G) of a graph G is the smallest number k such that G together with k isolated vertices added is the competition graph of an acyclic digraph. A chordless cycle of length at least 4 of a graph is called a hole of the graph. The number of holes of a graph is closely related to its competition number as the competition number of a graph which does not contain a hole is at most one and the competition number of a complete bipartite graph $K_{\lfloor \frac{n}{2} \rfloor, \lceil \frac{n}{2} \rceil}$ which has so many holes that no more holes can be added is the largest among those of graphs with n vertices. In this paper, we show that even if a connected graph G has many holes, the competition number of G can be as small as 2 under some assumption. In addition, we show that, for a connected graph G with exactly h holes and at most one non-edge maximal clique, if all the holes of G are pairwise edge-disjoint and the clique number $\omega = \omega (G)$ of G satisfies $2 \leq \omega \leq h+1$, then the competition number of G is at most $h - \omega + 3$.
Kim Seog-Jin
Kim Suh-Ryung
Lee Jung Yeun
Sano Yoshio
No associations
LandOfFree
Graphs having many holes but with small competition numbers 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 Graphs having many holes but with small competition numbers, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Graphs having many holes but with small competition numbers will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-664732