Abstract
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.
| Original language | English (US) |
|---|---|
| Pages (from-to) | 1381-1390 |
| Number of pages | 10 |
| Journal | Discrete Applied Mathematics |
| Volume | 159 |
| Issue number | 14 |
| DOIs | |
| State | Published - Aug 28 2011 |
Funding
This research was conducted at the 2010 Research Experience for Undergraduates Program at the University of Minnesota Duluth [UMD], under the guidance of Joseph Gallian. This program was funded by the National Science Foundation , the Department of Defense , the National Security Agency , and UMD . The author would like to thank Maria Monks for her support and guidance, and Geir Helleloid and Eric Riedl for offering many helpful suggestions about this presentation.
Keywords
- Competition graph
- Digraph
- Path
ASJC Scopus subject areas
- Discrete Mathematics and Combinatorics
- Applied Mathematics