A new sufficient condition for a Digraph to be Hamiltonian-A proof of Manoussakis Conjecture
Discrete mathematics & theoretical computer science, Tome 22 (2020-2021) no. 4
Voir la notice de l'article provenant de la source Episciences
Y. Manoussakis (J. Graph Theory 16, 1992, 51-59) proposed the following conjecture. \noindent\textbf{Conjecture}. {\it Let $D$ be a 2-strongly connected digraph of order $n$ such that for all distinct pairs of non-adjacent vertices $x$, $y$ and $w$, $z$, we have $d(x)+d(y)+d(w)+d(z)\geq 4n-3$. Then $D$ is Hamiltonian.} In this paper, we confirm this conjecture. Moreover, we prove that if a digraph $D$ satisfies the conditions of this conjecture and has a pair of non-adjacent vertices $\{x,y\}$ such that $d(x)+d(y)\leq 2n-4$, then $D$ contains cycles of all lengths $3, 4, \ldots , n$.
@article{DMTCS_2020_22_4_a11,
author = {Darbinyan, Samvel Kh.},
title = {A new sufficient condition for a {Digraph} to be {Hamiltonian-A} proof of {Manoussakis} {Conjecture}},
journal = {Discrete mathematics & theoretical computer science},
publisher = {mathdoc},
volume = {22},
number = {4},
year = {2020-2021},
doi = {10.23638/DMTCS-22-4-12},
language = {en},
url = {http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-22-4-12/}
}
TY - JOUR AU - Darbinyan, Samvel Kh. TI - A new sufficient condition for a Digraph to be Hamiltonian-A proof of Manoussakis Conjecture JO - Discrete mathematics & theoretical computer science PY - 2020-2021 VL - 22 IS - 4 PB - mathdoc UR - http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-22-4-12/ DO - 10.23638/DMTCS-22-4-12 LA - en ID - DMTCS_2020_22_4_a11 ER -
%0 Journal Article %A Darbinyan, Samvel Kh. %T A new sufficient condition for a Digraph to be Hamiltonian-A proof of Manoussakis Conjecture %J Discrete mathematics & theoretical computer science %D 2020-2021 %V 22 %N 4 %I mathdoc %U http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-22-4-12/ %R 10.23638/DMTCS-22-4-12 %G en %F DMTCS_2020_22_4_a11
Darbinyan, Samvel Kh. A new sufficient condition for a Digraph to be Hamiltonian-A proof of Manoussakis Conjecture. Discrete mathematics & theoretical computer science, Tome 22 (2020-2021) no. 4. doi: 10.23638/DMTCS-22-4-12
Cité par Sources :