Competition numbers of complete r r -partite graphs
The competition graph C(D) C ( D ) of an acyclic digraph D D is the graph with the same vertex set as D D and two distinct vertices x x and y y are adjacent in C(D) C ( D ) if and only if there is a vertex v v in D D such that (x,v) ( x , v ) and (y,v) ( y , v ) are arcs of D D . The competition number ?(G) ? ( G ) of a graph G G is the minimum number of isolated vertices that must be added to G G to form the competition graph of an acyclic digraph. In this paper, we investigate competition numbers of complete r r -partite graphs Kn1,n2,,nr K n 1 , n 2 ,  , n r . In particular, we determine the numbers for r=3 r = 3 and for some cases of r?4 r ? 4 . We also give bounds for the competition numbers of general complete r r -partite graphs.
competition number competition graph complete r r -partite graph r r r r r latin square