Abstract
The competition graph and its generalizations have interested graph theorists for over 30 years. Recently, Cho, Kim, and Nam introduced the m-step competition graph and computed the 2-step competition numbers of paths and cycles. We extend their results in a partial determination of the m-step competition numbers of paths and cycles. In addition, we introduce two new variants of competition graphs: same-step and any-step. We classify same-step and any-step competition graphs and investigate their related competition numbers.
| Original language | English (US) |
|---|---|
| Pages (from-to) | 159-175 |
| Number of pages | 17 |
| Journal | Discrete Applied Mathematics |
| Volume | 152 |
| Issue number | 1-3 |
| DOIs | |
| State | Published - Nov 1 2005 |
All Science Journal Classification (ASJC) codes
- Discrete Mathematics and Combinatorics
- Applied Mathematics
Keywords
- Any-step competition graph
- Competition graph
- Competition number
- m-step competition graph
- Same-step competition graph