Nebraska Conference for Undergraduate Women in Mathematics

In 2013, Factor, Merz and Sano asked the question: Are there graphs other than C_{4}, the cycle on 4 vertices, where the competition number of a graph G, denoted k(G), is greater than its (1,2)-step competition number, k(1,2)(G)? The competition number k(G) is defined as the smallest nonnegative integer k such that a graph G with k isolated vertices is the competition graph for some acyclic digraph. Similarly, the (1,2)-step competition number is defined as the smallest nonnegative integer k such that a graph G with k isolated vertices is the (1,2)-step competition graph for some acyclic digraph D. An (i,j)-step competition graph is the generalized concept in which {x,y} will be an edge in the (i, m)-step competition graph, denoted C(i,m)(D), if for some  z ∈ V(D)-{x,y}, d_{D-y} (x,z) ≤ 1 and d_{D-x}(y,z) ≤ 2 or d_{D-x}(y,z) ≤ 1 and d_{D-y}(x,z) ≤ 2. Here we explore classes of graphs that provide a partial answer to the question asked in that paper and prove that the relationship exists.