Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
420214 | Discrete Applied Mathematics | 2011 | 10 Pages |
Abstract
For any digraph DD let the mm-step competition graph Cm(D)Cm(D) be the graph with the same vertices as DD where xx and yy share an edge in Cm(D)Cm(D) if in DD there are mm-step paths from xx and yy to a common vertex zz. This paper builds on the work of G.T. Helleloid (2005) and J. Kuhl and B.C. Swan (2010), characterizing the paths that are mm-step competition graphs of a digraph. We show that the nn-step path PnPn is an mm-step competition graph if and only if either m∣n−1m∣n−1 or m∣n−2m∣n−2.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Eva Belmont,