The competition numbers of complete multipartite graphs with many partite sets

The competition graph of a digraph DD is a graph which has the same vertex set as DD and has an edge between two vertices uu and vv if and only if there exists a vertex xx in DD such that (u,x)(u,x) and (v,x)(v,x) are arcs of DD. For any graph GG, GG together with sufficiently many isolated vertices is the competition graph of some acyclic digraph. The competition number k(G)k(G) of a graph GG 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.