Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
10328727 | Discrete Applied Mathematics | 2005 | 8 Pages |
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.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Geir T. Helleloid,