Paper Info
Title
Connected triangle-free m-step competition graphs
Abstract
In 1968, Cohen presented competition graphs in connection with the study of ecological systems. Recently, Cho, Kim and Nam introduced a generalization called the m-step competition graph. In this paper, we characterize connected triangle-free m-step competition graphs on n vertices for m≥n. The analogous result follows for same-step competition graphs. We also demonstrate that the path on n vertices is an (n - 1)-step and an (n - 2)-step competition graph. Finally, we resolve a question of Cho, Kim and Nam on an inequality between 1-step and m-step competition numbers.
Year
DOI
Venue
2005
10.1016/j.dam.2004.06.010
Discrete Applied Mathematics
Keywords
Field
DocType
ecological system,n vertex,connected triangle-free m-step competition,analogous result,step competition graph,m-step competition graph,competition graph,triangle-free m-step competition graph,m -step competition graph,m -step competition number,same-step competition graph,m-step competition number
Discrete mathematics,Graph,Combinatorics,Indifference graph,Modular decomposition,Vertex (geometry),Chordal graph,Competition number,Pathwidth,Pancyclic graph,Mathematics
Journal
Volume
Issue
ISSN
145
3
Discrete Applied Mathematics
Citations 
PageRank 
References 
8
0.96
2
Authors
1
Name
Order
Citations
PageRank
Geir T. Helleloid1101.73