Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
9512161 | Discrete Mathematics | 2005 | 10 Pages |
Abstract
Let D be an acyclic digraph. The competition graph of D has the same set of vertices as D and an edge between vertices u and v if and only if there is a vertex x in D such that (u,x) and (v,x) are arcs of D. The competition number of a graph G, denoted by k(G), is the smallest number k such that G together with k isolated vertices is the competition graph of an acyclic digraph. In this paper, we show that the competition number of a graph having exactly one chordless cycle of length at least 4 is at most two. We also give a large family of such graphs whose competition numbers are less than or equal to one.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Han Hyuk Cho, Suh-Ryung Kim,