Samvel Kh. Darbinyan - A new sufficient condition for a Digraph to be Hamiltonian-A proof of Manoussakis Conjecture

dmtcs:6086 - Discrete Mathematics & Theoretical Computer Science, January 18, 2021, vol. 22 no. 4 - https://doi.org/10.23638/DMTCS-22-4-12
A new sufficient condition for a Digraph to be Hamiltonian-A proof of Manoussakis ConjectureArticle

Authors: Samvel Kh. Darbinyan

    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$.


    Volume: vol. 22 no. 4
    Section: Graph Theory
    Published on: January 18, 2021
    Accepted on: November 5, 2020
    Submitted on: February 11, 2020
    Keywords: Mathematics - Combinatorics

    Consultation statistics

    This page has been seen 473 times.
    This article's PDF has been downloaded 176 times.