On competition numbers of complete multipartite graphs with partite sets of equal size
Boram Park, Suh-Ryung Kim, Yoshio Sano · 2008
Let D be an acyclic digraph. The competition graph of D is a 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, G together with sufficiently many isolated vertices is the competition graph of some acyclic digraph. The competition number k(G) of G is the smallest number of such isolated vertices. In general, it is hard to compute the competition number k(G) for a graph G and it has been one of important research problems in the study of competition graphs to characterize a graph by its competition number. In this paper, we compute the competition numbers of a complete multipartite graph in which each partite set has two vertices and a complete multipartite graph in which each partite set has three vertices.