Article ID Journal Published Year Pages File Type
4646992 Discrete Mathematics 2016 6 Pages PDF
Abstract

Let D=(V(D),A(D))D=(V(D),A(D)) be a digraph and kk be an integer with k≥2k≥2. A digraph DD is kk-quasi-transitive, if for any path x0x1…xkx0x1…xk of length kk, x0x0 and xkxk are adjacent. In this paper, we consider the traceability of kk-quasi-transitive digraphs with even k≥4k≥4. We prove that a strong kk-quasi-transitive digraph DD with even k≥4k≥4 and diam(D)≥k+2 has a Hamiltonian path. Moreover, we show that a strong kk-quasi-transitive digraph DD such that either kk is odd or k=2k=2 or diam(D)

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, ,