k ‐quasi‐transitive digraphs of large diameter

Given an integer k with k ≥ 2 , a digraph D = ( V D , A D ) is k ‐quasi‐transitive if for every u v ‐directed path of length k in D , we have ( u , v ) ∈ A D or ( v , u ) ∈ A D (or both). In this study, we prove that if k is an odd integer, k ≥ 5 , then every strong k ‐quasi‐transitive digraph of diameter at least k + 2 admits a partition of its vertex set V D = ( V 1 , V 2 ) such that D [ V 1 ] is Hamiltonian, and both D [ V 1 ] and D [ V 2 ] are semicomplete bipartite, when D is bipartite, or semicomplete, otherwise. As a consequence, for an odd integer k ≥ 3 , it is easy to prove that every non‐bipartite strong k ‐quasi‐transitive digraph with diameter at least k + 2 has a Hamiltonian path.