Metadata language
Անվանում:
On a Problem of Wang Concerning the H amiltonicityof Bipartite Digraphs ; О задаче Ванга о гамильтоновости двудольных орграфов
Հեղինակ:
Darbinyan Samvel ; Дарбинян Самжел
Տեսակ:
Համահեղինակ(ներ):
Karapetyan Iskandar ; Карапетян Искандар
Չվերահսկվող բանալի բառեր:
Digraph ; cycle factor ; Hamiltonian cycle ; Bipartite balanced digraph ; perfect matching
Ամփոփում:
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 является доминирующим паром.
Հրատարակիչ:
"GITUTYUN" PUBLISHING HOUSE OF NAS RA ; Издательство "Гитутюн" НАН РА
ISSN:
Լեզու:
Ամսագրի կամ հրապարակման վերնագիր:
Mathematical Problems of Computer Science 4
Հատոր:
URL:
լրացուցիչ տեղեկատվություն:
amdarbin@ipia.sci.am ; isko@ipia.sci.am
Կազմակերպության անվանում:
Institute for Informatics and Automation Problems