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

The competition graph of a digraph D is the graph which has the same vertex set as D and has an edge between 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, the disjoint union of G 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) of G. In general, it is hard to compute the competition number k(G) for a graph G 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. (C) 2009 Elsevier B.V. All rights reserved.