Open AccessOn the Manoussakis Conjecture for a Digraph to be Hamiltonian
Author(s) -
Samvel Kh. Darbinyan
Publication year - 2019
Publication title -
mathematical problems of computer science
Language(s) - English
Resource type - Journals
eISSN - 2738-2788
pISSN - 2579-2784
DOI - 10.51408/1963-0031
Subject(s) - conjecture , combinatorics , digraph , hamiltonian (control theory) , mathematics , hamiltonian path , graph , order (exchange) , discrete mathematics , physics , mathematical optimization , finance , economics
Manoussakis (J. Graph Theory 16, 1992, 51-59) proposed the following conjecture. Conjecture. 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) ≥ 4n − 3. Then D is Hamiltonian. In this note, we prove that if D satisfies the conditions of this conjecture, then (i) D has a cycle factor; (ii) If {x, y} is a pair of non-adjacent vertices of D such that d(x) + d(y) ≤ 2n − 2, then D is Hamiltonian if and only if D contains a cycle passing through x and y; (iii) If {x, y} a pair of non-adjacent vertices of D such that d(x)+d(y) ≤ 2n−4, then D contains cycles of all lengths 3, 4, . . . , n−1; (iv) D contains a cycle of length at least n − 1