Metadata language
Title:
On Cyclability of Digraphs with a Manoussakis-typeCondition ; О цикличности орграфов при условий типа Маноусакиса
Author:
Darbinyan Samvel ; Дарбинян Самвел
Type:
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:
Language:
Journal or Publication Title:
Mathematical Problems of Computer Science
Volume:
Additional Information:
Affiliation:
Institute for Informatics and Automation Problems of NAS RA