p-competition numbers

Suh ryung Kim, Terry A. McKee, F. R. McMorris, Fred S. Roberts

Research output: Contribution to journalArticlepeer-review

9 Scopus citations

Abstract

If D = (V, A>) is a digraph, its p-competition graph has vertex set V and an edge between x and y if and only if there are distinct vertices a1,...,ap in D with (x, ai) and (y,ai) arcs of D for each i ≤ p. The p-competition number of a graph is the smallest number of isolated vertices which need to be added in order to make it a p-competition graph. These notions generalize the widely studied p = 1 case, where they correspond to ordinary competition graphs and competition numbers. We obtain bounds on the p-competition number in terms of the ordinary competition number, and show that, surprisingly, the p-competition number can be arbitrarily smaller than the ordinary competition number.

Original languageEnglish (US)
Pages (from-to)87-92
Number of pages6
JournalDiscrete Applied Mathematics
Volume46
Issue number1
DOIs
StatePublished - Sep 21 1993

All Science Journal Classification (ASJC) codes

  • Discrete Mathematics and Combinatorics
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'p-competition numbers'. Together they form a unique fingerprint.

Cite this