Darbinyan, Samvel Kh. - 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 Conjecture

Authors: Darbinyan, Samvel Kh.

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
Submitted on: February 11, 2020
Keywords: Mathematics - Combinatorics


Share

Consultation statistics

This page has been seen 48 times.
This article's PDF has been downloaded 13 times.