DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

IMPACT FACTOR 2018: 0.741

SCImago Journal Rank (SJR) 2018: 0.763

Rejection Rate (2017-2018): c. 84%

Discussiones Mathematicae Graph Theory

Article in press


Authors:

R.X. Wang

Title:

Hamilton cycle problem in strong $k$-quasi-transitive digraphs with large diameter

Source:

Discussiones Mathematicae Graph Theory

Received: 2018-05-09, Revised: 2018-05-09, Accepted: 2018-11-05, https://doi.org/10.7151/dmgt.2187

Abstract:

Let $k$ be an integer with $k\geq 2$. A digraph is $k$-quasi-transitive, if for any path $x_0x_1\ldots x_k$ of length $k$, $x_0$ and $x_k$ are adjacent. Let $D$ be a strong $k$-quasi-transitive digraph with even $k\ge 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\ge 6$ and give the sufficient condition for $D$ to be Hamiltonian.

Keywords:

quasi-transitive digraph, $k$-quasi-transitive digraph, Hamiltonian cycle

PDF
Close