Geodesic
Hamiltonian Cycle Problem in Strong k-Quasi-Transitive Digraphs with Large Diameter
Discussiones Mathematicae. Graph Theory, Tome 41 (2021) no. 2, pp. 685-690 Cet article a éte moissonné depuis la source Library of Science

Voir la notice de l'article

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: quasi-transitive digraph, k -quasi-transitive digraph, Hamiltonian cycle 
@article{DMGT_2021_41_2_a20,
     author = {Wang, Ruixia},
     title = {Hamiltonian {Cycle} {Problem} in {Strong} {k-Quasi-Transitive} {Digraphs} with {Large} {Diameter}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {685--690},
     year = {2021},
     volume = {41},
     number = {2},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2021_41_2_a20/}
}
TY  - JOUR
AU  - Wang, Ruixia
TI  - Hamiltonian Cycle Problem in Strong k-Quasi-Transitive Digraphs with Large Diameter
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2021
SP  - 685
EP  - 690
VL  - 41
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/DMGT_2021_41_2_a20/
LA  - en
ID  - DMGT_2021_41_2_a20
ER  - 
%0 Journal Article
%A Wang, Ruixia
%T Hamiltonian Cycle Problem in Strong k-Quasi-Transitive Digraphs with Large Diameter
%J Discussiones Mathematicae. Graph Theory
%D 2021
%P 685-690
%V 41
%N 2
%U http://geodesic.mathdoc.fr/item/DMGT_2021_41_2_a20/
%G en
%F DMGT_2021_41_2_a20
Wang, Ruixia. Hamiltonian Cycle Problem in Strong k-Quasi-Transitive Digraphs with Large Diameter. Discussiones Mathematicae. Graph Theory, Tome 41 (2021) no. 2, pp. 685-690. http://geodesic.mathdoc.fr/item/DMGT_2021_41_2_a20/

[1] J. Bang-Jensen and G. Gutin, Digraphs: Theory, Algorithms and Applications (Springer-Verlag, London, 2000).

[2] C. Hernández-Cruz and H. Galeana-Sánchez, k-kernels in k-transitive and k-quasi-transitive digraphs, Discrete Math. 312 (2012) 2522–2530. doi:10.1016/j.disc.2012.05.005

[3] H. Galeana-Sánchez. I.A. Goldfeder and I. Urrutia, On the structure of strong 3-quasi-transitive digraphs, Discrete Math. 310 (2010) 2495–2498. doi:10.1016/j.disc.2010.06.008

[4] H. Galeana-Sánchez, C. Hernández-Cruz and M.A. Juárez-Camacho, On the existence and number of (k +1)-kings in k-quasi-transitive digraphs, Discrete Math. 313 (2013) 2582–2591. doi:10.1016/j.disc.2013.08.007

[5] R. Wang and W. Meng, k-kings in k-quasitransitive digraphs, J. Graph Theory 79 (2015) 55–62. doi:10.1002/jgt.21814

[6] R. Wang, ( k +1)- kernels and the number of k-kings in k-quasi-transitive digraphs, Discrete Math. 338 (2015) 114–121. doi:10.1016/j.disc.2014.08.009

[7] R. Wang and H. Zhang, Hamiltonian paths in k-quasi-transitive digraphs, Discrete Math. 339 (2016) 2094–2099. doi:10.1016/j.disc.2016.02.020