Abstract
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) |
|---|---|
| Pages (from-to) | 161-173 |
| Number of pages | 13 |
| Journal | Ars Combinatoria |
| Volume | 63 |
| State | Published - Apr 2002 |
All Science Journal Classification (ASJC) codes
- Mathematics(all)