The (l,m)-step Competition Number of a Graph

Kim Factor, Marquette University
Sarah Merz, The University of the Pacific
Yoshio Sano, Pohang Mathematics Institute

Presented at the 42nd International Conference on Combinatorics, Graph Theory and Computing, Florida Atlantic University in Boca Raton, Florida, March 2011


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.