View article

A digraph is quasi‐transitive if there is a complete adjacency between the inset and the outset of each vertex. Quasi‐transitive digraphs are interseting because of their relation to comparability graphs. Specifically, a graph can be oriented as a quasi‐transitive digraph if and only if it is a comparability graph. Quasi‐transitive digraphs are also of interest as they share many nice properties of tournaments. Indeed, we show that every strongly connected quasi‐transitive digraphs D on at least four vertices has two vertices v₁ and v₂ such that D – v_i is strongly connected for i = 1, 2. A result of tournaments on the existence of a pair of arc‐disjoint in‐ and out‐branchings rooted at the same vertex can also be extended to quasi‐transitive digraphs. However, some properties of tournaments, like hamiltonicity, cannot be extended directly to quasi‐transitive digraphs. Therefore we characterize those quasi‐transitive digraphs …