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 language||English (US)|
|Number of pages||13|
|State||Published - Apr 2002|
All Science Journal Classification (ASJC) codes