QUASI-TRANSITIVE DIGRAPHS

A digraph is quasi-transitive if there is a complete adjacency between the inset and the outset of each vertex. Quasi-transitive digraphs ar e interesting because of their relation to comparability graphs. Speci fically, a graph can be oriented as a quasi-transitive digraph if and only if it is a comparability graph. Quasi-transitive digraphs are als o of interest as they share many nice properties of tournaments. Indee d, we show that every strongly connected quasi-transitive digraph D on at least four vertices has two vertices v(1) and v(2) such that D - v (i) is strongly connected for i = 1,2. A result of tournaments on the existence of a pair of are-disjoint in- and out-branchings rooted at t he same vertex can also be extended to quasi-transitive digraphs. Howe ver, some properties of tournaments, like hamiltonicity, cannot be ext ended directly to quasi-transitive digraphs. Therefore we characterize those quasi-transitive digraphs which have a hamiltonian cycle, respe ctively a hamiltonian path. We show the existence of highly connected quasi-transitive digraphs D with a factor (a collection of disjoint cy cles covering the vertex set of D), which have a cycle of every length 3 less than or equal to k less than or equal to\V(D)\ - 1 through eve ry vertex and yet they are not hamiltonian. Finally we characterize pa ncyclic and vertex pancyclic quasi-transitive digraphs. (C) 1995, John Wiley & Sons, Inc.