Competition Graphs of Acyclic Digraphs Satisfying Condition \(C^*(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^*(p)\). While they could completely characterize the competition graph of an acyclic digraph satisfying \(C(p)\), they obtained only partial results on \(C^*(p)\) and left the general case open. In this paper, we answer their open question.