Which digraphs are round
Jing Huang · 1999
A digraph D is round if the vertices of D can be circularly ordered as VI, V2,..., Vn so that, for each vertex Vi, the out-neighbours of Vi appear consecutively following Vi and the in-neighbours of Vi appear consecutively preceding Vi in the ordering. We characterize round digraphs in terms of forbidden substructures. Our proof implies a polynomial algorithm to decide if a digraph is round. 1 The theorem We assume that a digraph has no loops or multiple arcs but may contain a cycle of length 2. If it contains no cycle of length 2, then it is an oriented graph. Let D be a digraph. We say that a vertex x is adjacent to a vertex y in D if there is at least one arc between x and y. If xy is an arc of D, then we say that x dominates y and use the notation x-t y to denote this. If x-t y, then y is an out-neighbour of x and x is an in-neighbour of y. The set O(x) of all out-neighbours of x is called the outset of x and the set I(x) of all in-neighbour of x is called the