The competition numbers of complete multipartite graphs and mutually orthogonal Latin squares

The competition graph of a digraph DD is the graph which has the same vertex set as DD and has an edge between 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, the disjoint union of GG and sufficiently many isolated vertices is the competition graph of some acyclic digraph. The smallest number of isolated vertices needed is defined to be the competition number k(G)k(G) of GG. In general, it is hard to compute the competition number k(G)k(G) for a graph GG and it is an important research problem in the study of competition graphs to characterize the competition graphs of acyclic digraphs by computing their competition numbers. In this paper, we give new upper and lower bounds for the competition number of a complete multipartite graph in which all partite sets have the same size by using orthogonal Latin squares. When there are exactly four partite sets, we give better bounds.