The m-step, same-step, and any-step competition graphs

Research output: Contribution to journalArticlepeer-review

12 Scopus citations


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 languageEnglish (US)
Pages (from-to)159-175
Number of pages17
JournalDiscrete Applied Mathematics
Issue number1-3
StatePublished - Nov 1 2005

All Science Journal Classification (ASJC) codes

  • Discrete Mathematics and Combinatorics
  • Applied Mathematics


  • Any-step competition graph
  • Competition graph
  • Competition number
  • m-step competition graph
  • Same-step competition graph


Dive into the research topics of 'The m-step, same-step, and any-step competition graphs'. Together they form a unique fingerprint.

Cite this