Authors: R.X. Wang Title: Hamilton cycle problem in strong k-quasi-transitive digraphs with large diameter Source: Discussiones Mathematicae Graph Theory Received 09.05.2018, Revised 09.05.2018, Accepted 05.11.2018, doi: 10.7151/dmgt.2187 | |
Abstract: Let k be an integer with k≥ 2. A digraph is k-quasi-transitive, if for any path x_{0}x_{1}... x_{k} of length k, x_{0} and x_{k} 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: quasi-transitive digraph, k-quasi-transitive digraph, Hamiltonian cycle | |
Links: |