Competition Graphs of Semiorders and the Conditions \(C(p)\) and \(C^*(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^*(p)\) and to study the graphs arising as competition graphs of acyclic digraphs satisfying conditions \(C(p)\) or \(C^*(p)\).