Competition Graphs of Semiorders and the Conditions $C(p)$ and $C^{\ast }(p)$

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 condition on digraphs called $C(p)$ and $C^{\ast }(p)$ and to study the graphs arising as competition graphs of acyclic digraphs satisfying conditions $C(p)$ or $C^{\ast }(p)$.