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

Eva Belmont

doi:10.1016/j.dam.2011.04.026

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

Eva Belmont^*

^*Corresponding author for this work

Mathematics

Research output: Contribution to journal › Article › peer-review

7 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 language	English (US)
Pages (from-to)	1381-1390
Number of pages	10
Journal	Discrete Applied Mathematics
Volume	159
Issue number	14
DOIs	https://doi.org/10.1016/j.dam.2011.04.026
State	Published - Aug 28 2011

Keywords

Competition graph
Digraph
Path

ASJC Scopus subject areas

Discrete Mathematics and Combinatorics
Applied Mathematics

Access to Document

10.1016/j.dam.2011.04.026

Cite this

@article{d2f81cd017994807a0a86c4444474ec5,

title = "A complete characterization of paths that are m-step competition graphs",

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.",

keywords = "Competition graph, Digraph, Path",

author = "Eva Belmont",

note = "Funding Information: 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. ",

year = "2011",

month = aug,

day = "28",

doi = "10.1016/j.dam.2011.04.026",

language = "English (US)",

volume = "159",

pages = "1381--1390",

journal = "Discrete Applied Mathematics",

issn = "0166-218X",

publisher = "Elsevier",

number = "14",

}

TY - JOUR

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

AU - Belmont, Eva

N1 - Funding Information: 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.

PY - 2011/8/28

Y1 - 2011/8/28

N2 - 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.

AB - 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.

KW - Competition graph

KW - Digraph

KW - Path

UR - http://www.scopus.com/inward/record.url?scp=79960593990&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=79960593990&partnerID=8YFLogxK

U2 - 10.1016/j.dam.2011.04.026

DO - 10.1016/j.dam.2011.04.026

M3 - Article

AN - SCOPUS:79960593990

SN - 0166-218X

VL - 159

SP - 1381

EP - 1390

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

IS - 14

ER -

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

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this