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