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.
- Competition graph
ASJC Scopus subject areas
- Discrete Mathematics and Combinatorics
- Applied Mathematics