Journal of Graph Theory · 1995 · 110 citations · 14 references
Natural SciencesMathematicsCombinatoricsGame TheoryTopologyDirected Acyclic GraphsGraph AlgorithmsGraph TheoryComparability GraphsHamiltonian CyclesHamiltonian Path ProblemHamiltonian PathsStrongly Connected Components
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 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 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.
14
Hamiltonian-connected tournaments
Carsten Thomassen · Journal of Combinatorial Theory Series B · 1980 · 122 citations