Co-author(s) :

Karapetyan Iskandar ; Карапетян Искандар

Abstract:

R. Wang (Discrete Mathematics and Theoretical Computer Science, vol. 19(3), 2017) proposed the following problem. Problem. Let D be a strongly connected balanced bipartite directed graph of order 2a ≥8. Suppose that d(x) ¸ 2a - k, d(y) ¸ a + k or d(y) ≥ 2a - k, d(x) ¸ a + k for every pair of vertices fx; yg with a common out-neighbour, where 2  k · a=2. Is D Hamiltonian? In this paper, we prove that if a digraph D satisfies the conditions of this problem, then (i) D contains a cycle factor, (ii) for every vertex x  V (D) there exists a vertex y  V (D) such that x and y have a common out-neighbour.
; Ванг (Discrete Mathematics and Theoretical Computer Science, vol. 19(3) 2017) предложила следующую задачу. Задача: Пусть D -2а -вершинный 2a > 8 сильносвязный сбалансированный двудольный орграф, в котором для любой пары доминирующих вершин {x,yg, d(x) > 2а — k, d(y) > a + k или d(y) > a + k, d(y) > 2a — k, где 2 < k < a/2. Является ли D гамильтоновым? В настоящей работе доказано, что если орграф D удовлетворяет условиям задачи Ванга, то (i) D содержит цикл-фактор и не-гамильтоновый цикл длины по крайней мере 4, (ii) для каждой вершины x существует такая вершина y, что {.x,yg является доминирующим паром.

Publisher:

"GITUTYUN" PUBLISHING HOUSE OF NAS RA ; Издательство "Гитутюн" НАН РА

Identifier:

oai:noad.sci.am:135883

ISSN:

0131-4645

Language:

English ; Английский

Journal or Publication Title:

Mathematical Problems of Computer Science 4

Volume:

49

URL:

Additional Information:

amdarbin@ipia.sci.am ; isko@ipia.sci.am

Affiliation:

Institute for Informatics and Automation Problems

Country:

Armenia

Indexing:

ASCI