Competition Graphs of Semiorders and the Conditions C(p) and C*(p)

Suh Ryung Kim, Fred S. Roberts

Research output: Contribution to journalArticlepeer-review

9 Scopus citations


Given a digraph D, its competition graph has the same vertex set and an edge between two vertices x and y if there is a vertex u so that (x, u) and (y, u) are arcs of D. Motivated by a problem of communications, we study the competition graphs of the special digraphs known as semiorders. This leads us to define a conditions on digraphs called C(p) and C*(p) and to study the graphs arising as competition graphs of acyclic digraphs satisfying conditions C(p) or C*(p).

Original languageEnglish (US)
Pages (from-to)161-173
Number of pages13
JournalArs Combinatoria
StatePublished - Apr 2002

All Science Journal Classification (ASJC) codes

  • Mathematics(all)


Dive into the research topics of 'Competition Graphs of Semiorders and the Conditions C(p) and C*(p)'. Together they form a unique fingerprint.

Cite this