The competition number of a graph with exactly two holes

Details The competition number of a graph with exactly two holes The competition number of a graph with exactly two holes

2009-09-29

arxiv.org/abs/0909.5302v1

Ars Combinatoria 95 (2010) 45-54

Mathematics

Combinatorics

10 pages

Scientific paper

Let D be an acyclic digraph. The competition graph of D is a 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. A hole of a graph is a cycle of length at least 4 as an induced subgraph. In 2005, Kim [5] conjectured that the competition number of a graph with h holes is at most h+1. Though Li and Chang [8] and Kim et al. [7] showed that her conjecture is true when the holes do not overlap much, it still remains open for the case where the holes share edges in an arbitrary way. In order to share an edge, a graph must have at least two holes and so it is natural to start with a graph with exactly two holes. In this paper, the conjecture is proved true for such a graph.

Affiliated with

Also associated with

No associations

Rating

The competition number of a graph with exactly two holes 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 The competition number of a graph with exactly two holes, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The competition number of a graph with exactly two holes will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-664696