Hamiltonian paths in -quasi-transitive digraphs

详细信息    查看全文

• 作者：Ruixia Wang ; ^{wangrx@sxu.edu.cn" class="auth_mail" title="E-mail the corresponding author} ; Hui Zhang
• 关键词：Quasi-transitive digraph ; kk-quasi-transitive digraph ; Hamiltonian path
• 刊名：Discrete Mathematics
• 出版年：2016
• 出版时间：6 August 2016
• 年：2016
• 卷：339
• 期：8
• 页码：2094-2099
• 全文大小：367 K

文摘

Let D=(V(D),A(D))$D=(V\left(D\right),A\left(D\right))$ be a digraph and k$k$ be an integer with a62c285c9073fdfeeecf24ada5ebae97" title="Click to view the MathML source">k≥2$k\ge 2$. A digraph D$D$ is k$k$-quasi-transitive, if for any path x₀x₁…x_k$x_0{x}_1\dots x_k$ of length k$k$, x₀$x_0$ and x_k$x_k$ are adjacent. In this paper, we consider the traceability of k$k$-quasi-transitive digraphs with even 47a05bfcaaca9d4d4" title="Click to view the MathML source">k≥4$k\ge 4$. We prove that a strong k$k$-quasi-transitive digraph D$D$ with even 47a05bfcaaca9d4d4" title="Click to view the MathML source">k≥4$k\ge 4$ and $\mathrm{diam}\left(D\right)\ge k+2$ has a Hamiltonian path. Moreover, we show that a strong k$k$-quasi-transitive digraph D$D$ such that either k$k$ is odd or k=2$k=2$ or $\mathrm{diam}\left(D\right)<k+2$ may not contain Hamiltonian paths.