Quasi‐transitive digraphs
Jørgen Bang‐Jensen, Jing Huang · Journal of Graph Theory · 1995
Abstract 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 v1 and v2 such that D – vi 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 which have a hamiltonian cycle, respectively a hamiltonian path. We show the existence of highly connected quasi‐transitive digraphs D with a factor (a collection of disjoint cycles covering the vertex set of D), which have a cycle of every length 3 ≦ k ≦ |V(D)| − 1 through every vertex and yet they are not hamiltonian. Finally we characterize pancyclic and vertex pancyclic quasi‐transitive digraphs. © 1995, John Wiley & Sons, Inc.