Discussiones Mathematicae Graph Theory (May 2021)

Hamiltonian Cycle Problem in Strong k-Quasi-Transitive Digraphs With Large Diameter

  • Wang Ruixia

DOI
https://doi.org/10.7151/dmgt.2187
Journal volume & issue
Vol. 41, no. 2
pp. 685 – 690

Abstract

Read online

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.

Keywords