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

作者：Belmont Eva^*

来源：Discrete Applied Mathematics, 2011, 159(14): 1381-1390.

DOI：10.1016/j.dam.2011.04.026

• Competition graph
• Path
• Digraph

For any digraph D let the m-step competition graph C(m)(D) be the graph with the same vertices as D where x and y share an edge in C(m) (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 P(n) is an m-step competition graph if and only if either in vertical bar n - 1 or m vertical bar n - 2.

• 出版日期2011-8-28