A complete characterization of paths that are m-step competition graphs

Publication year: 2011
Source: Discrete Applied Mathematics, In Press, Corrected Proof, Available online 14 June 2011

Eva, Belmont

For any digraph D let the m-step competition graph Cm(D) be the graph with the same vertices as D where x and y share an edge in Cm(D) if in D there are m-step paths from x and y to a common vertex z. This paper builds on the work of G.T. Helleloid (2005) and J. Kuhl and B.C. Swan (2010), characterizing the paths that are m-step competition graphs of a digraph. We show that the n-step path Pn is an m-step competition graph if and only if either m∣n−1 or m∣n−2.