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

Eva Belmont*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

5 Scopus citations

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 languageEnglish (US)
Pages (from-to)1381-1390
Number of pages10
JournalDiscrete Applied Mathematics
Volume159
Issue number14
DOIs
StatePublished - Aug 28 2011

Keywords

  • Competition graph
  • Digraph
  • Path

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics
  • Applied Mathematics

Fingerprint Dive into the research topics of 'A complete characterization of paths that are m-step competition graphs'. Together they form a unique fingerprint.

Cite this