Article ID Journal Published Year Pages File Type
9512161 Discrete Mathematics 2005 10 Pages PDF
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
, ,