Competition Graphs of Acyclic Digraphs Satisfying Condition $C^{\ast }(p)$

Abstract

Given a digraph $D$, its competition graph $C(D)$ has the same vertex set as $D$ 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, Kim and Roberts [2002] studied the competition graphs of the special digraphs known as semiorders and the graphs arising as competition graphs of acyclic digraphs satisfying conditions so called $C(p)$ or $C^{\ast }(p)$. While they could completely characterize the competition graph of an acyclic digraph satisfying $C(p)$, they obtained only partial results on $C^{\ast }(p)$ and left the general case open. In this paper, we answer their open question.