Geodesic
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$.
DOI : 10.23638/DMTCS-22-4-12
Classification : 05C20, 05C45 
@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. http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-22-4-12/

Cité par Sources :