The competition numbers of complete multipartite graphs with many partite sets

The competition graph of a digraph D is a graph which has the same vertex set as D and has an edge between two vertices u and v if and only if there exists a vertex x in D such that (u, x) and (v, x) 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 a graph G is defined to be the smallest number of such isolated vertices. In this paper, we study the competition numbers of complete multipartite graphs. We give upper bounds for the competition numbers of complete multipartite graphs with many partite sets, which extends a result given by Park et al. (2009) [4]. In fact, by using these upper bounds, we compute the exact competition numbers of complete multipartite graphs in which each partite set has two vertices and the competition numbers of complete multipartite graphs in which each partite set has three vertices. (C) 2011 Elsevier B.V. All rights reserved.