Title:

On Cyclability of Digraphs with a Manoussakis-typeCondition ; О цикличности орграфов при условий типа Маноусакиса

Author:

Darbinyan Samvel ; Дарбинян Самвел

Type:

Article ; Журнал

Uncontrolled Keywords:

Digraphs ; Cycles ; Hamiltonian cycles ; Cyclability

Abstract:

Let D be a digraph of order n ¸ 4 and Y be a non-empty subset of vertices of D. Let for any pair u, v of distinct vertices of Y the digraph D contain a path from u to v and a path from v to u. Suppose D satis¯es the following conditions for every triple x; y; z 2 Y such that x and y are nonadjacent: If there is no arc from x to z, then d(x) + d(y) + d +(x) + d ¡(z) ¸ 3n ¡ 2. If there is no arc from z to x, then d(x) + d(y) + d +(z) + d ¡(x) ¸ 3n ¡ 2. We prove that there is a directed cycle in D which contains all the vertices of Y , except possibly one. This result is best possible in some situations and gives an answer to a question of Li, Flandrin and Shu (Discrete Mathematics, 307 (2007) 1291-1297). ; В работе доказано, что если подмножество Y вершин орграфа D удовлетворяет достаточному условию гамильтоновсти Маноусакиса (J. Graph Theory, 16, 1992 ), то в D существует контур, который содержит по крайней мере \Y\ — 1 вершин подмножества Y . Полученный результат решает задачу Ли, Фландрин и Шу (Discrete Mathematics, 307, 2007).

Publisher:

On Cyclability of Digraphs with a Manoussakis-type Conditions

ISSN:

0131-4645

Language:

English

Journal or Publication Title:

Mathematical Problems of Computer Science

Volume:

47

Additional Information:

samdarbin@ipia.sci.am

Affiliation:

Institute for Informatics and Automation Problems of NAS RA

Country:

Armenia

Year:

2017

Indexing:

ASCI