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).
On Cyclability of Digraphs with a Manoussakis-type Conditions
oai:noad.sci.am:135980
Mathematical Problems of Computer Science
Institute for Informatics and Automation Problems of NAS RA
May 3, 2021
Jul 28, 2020
20
https://noad.sci.am/publication/149591
Edition name | Date |
---|---|
Самвел Дарбинян, О цикличности орграфов при условий типа Маноусакиса | May 3, 2021 |
Darbinyan Samvel Karapetyan Iskandar
Darbinyan Samvel Karapetyan Iskandar
Darbinyan Samvel Karapetyan Iskandar