The (l,m)-step Competition Number of a Graph
Presented at the 42nd International Conference on Combinatorics, Graph Theory and Computing, Florida Atlantic University in Boca Raton, Florida, March 2011
Abstract
Let distD(x,y) be the number of arcs in the shortest directed path from x to y in digraph D. The (l,m)-step competition graph of D, denoted by C(l,m)(D), is a graph with vertex set V (D) so that, for distinct vertices x and y, {x,y} is an edge in C(l,m)(D) if and only if for some vertex z in V (D), distD-y(x,z) ≤ l and distD-x(y,z)≤m. Here, we extend Fred Roberts' definition of the competition number k(G) of a graph G, and introduce the (l,m)-step competition number, k(l,m)(G). It is the minimum number k such that G with k isolated vertices is the (l,m)-step competition graph of an acyclic digraph.