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

Abstract

Let dist_D(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), dist_D-y(x,z) ≤ l and dist_D-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.