Abstract:

Y. Manoussakis (J. Graph Theory 16, 1992, 51-59) proposed the following conjec- ture. 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.
; Пусть D является 2-сильно связным n-вершинным орграфом, в котором для любых различных пар {x,y}, {n,v} несмежных вершин имеет место d(x) + d(y) + d(w) + d(z) > 4n — 3. Тогда D является гамильтоновым. В настоящей работе доказано, что если орграф D удовлетворяет условиям гипотеза Маноуссакиса, то (1). D содержит цикл-фактор; (2). Если для некоторой пары несмежных вершин x и y имеет место d(x) + d(y) < 2n — 2, то имеют место: (i) D является гамильтоновым тогда и только тогда, когда D содержит контур проходящий через вершин x и y, (ii) D является гамильтоновым или содержит контур длины n — 1, который проходит через вершину x (y) (в частности, D содержит контур длины по крайней мере n — 1); (3). Если для некоторой пары несмежных вершин x и y имеет место d(x) + d(y) < 2n — 4, то D содержит контур любой длины k, 3 < k < n — 1;(4). Доказаны ряд свойств для контуров длины от n — 5 до n — 1.

Date submitted:

14.12.2018

Date accepted:

18.04.2019

Identifier:

oai:noad.sci.am:136051

DOI:

10.51408/1963-0031

ISSN:

0131-4645

Other identifier:

UDC 519.1

Language:

English

Journal or Publication Title:

Mathematical Problems of Computer Science

Volume:

51

URL:

Additional Information:

samdarbin@ipia.sci.am

Affiliation:

Institute for Informatics and Automation Problems ; Институт проблем информатики и автоматизации

Country:

Armenia

Indexing:

ASCI