## DIMACS TR: 2000-09

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

### Authors: Suh-Ryung Kim and Fred S. Roberts

**
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)$.

Paper Available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2000/2000-09.ps.gz

DIMACS Home Page