Competition numbers of complete r-partite graphs
Journal
Discrete Applied Mathematics
Journal Volume
160
Journal Issue
15
Pages
2271-2276
Date Issued
2012
Author(s)
Abstract
The competition graph C(D) of an acyclic digraph D is the graph with the same vertex set as D and two distinct vertices x and y are adjacent in C(D) if and only if there is a vertex v in D such that (x,v) and (y,v) are arcs of D. The competition number κ(G) of a graph G is the minimum number of isolated vertices that must be added to G to form the competition graph of an acyclic digraph. In this paper, we investigate competition numbers of complete r-partite graphs K n1, n2,..., nr. In particular, we determine the numbers for r=3 and for some cases of r<4. We also give bounds for the competition numbers of general complete r-partite graphs. © 2012 Elsevier B.V. All rights reserved.
Type
journal article