Mathematics – Combinatorics
Scientific paper
2011-02-28
Mathematics
Combinatorics
29 pages, 14 figures, 1 table
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 important research problems in the study of competition graphs to characterize a graph by its competition number. A hole of a graph is a cycle of length at least 4 as an induced subgraph. It holds that the competition number of a graph cannot exceed one plus the number of its holes if G satisfies a certain condition. In this paper, we show that the competition number of a graph with exactly h holes any two of which share at most one edge is at most h+1, which generalizes the existing results on this subject.
Kim Suh-Ryung
Lee Jung Yeun
Sano Yoshio
No associations
LandOfFree
The competition number of a graph in which any two holes share at most one edge 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 in which any two holes share at most one edge, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The competition number of a graph in which any two holes share at most one edge will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-425899