P-COMPETITION NUMBERS

If D = (V, A) is a digraph, its p-competition graph has vertex set V a nd an edge between x and y if and only if there are distinct vertices a1, ... , a(p) in D with (x, a(i)) and (y, a(i)) arcs of D for each i less-than-or-equal-to p. The p-competition number of a graph is the sm allest number of isolated vertices which need to be added in order to make it a p-competition graph. These notions generalize the widely stu died p = 1 case, where they correspond to ordinary competition graphs and competition numbers. We obtain bounds on the p-competition number in terms of the ordinary competition number, and show that, surprising ly, the p-competition number can be arbitrarily smaller than the ordin ary competition number.