Hamilton cycle problem in strong k-quasi-transitive digraphs with large diameter
Discussiones Mathematicae Graph Theory
Received 09.05.2018, Revised 09.05.2018, Accepted 05.11.2018, doi: 10.7151/dmgt.2187
Let k be an integer with k≥ 2. A digraph is k-quasi-transitive, if for any path x0x1... xk of length k, x0 and xk are adjacent. Let D be a strong k-quasi-transitive digraph with even k≥ 4 and diameter at least k+2. It has been shown that D has a Hamiltonian path. However, the Hamiltonian cycle problem in D is still open. In this paper, we shall show that D may contain no Hamiltonian cycle with k≥ 6 and give the sufficient condition for D to be Hamiltonian.
quasi-transitive digraph, k-quasi-transitive digraph, Hamiltonian cycle