Journal or Publication Title:

Математические вопросы кибернетики и вычислительной техники=Կիբեռնետիկայի և հաշվողական տեխնիկայի մաթեմատիկական հարցեր=Mathematical problems of computer science

Date of publication:

2018

Volume:

49

ISSN:

0131-4645

Additional Information:

Դարբինյան Ս., Կարապետյան Ի., Дарбинян С., Карапетян И.

Other title:

Կողմնորոշված երկմասնյա գրաֆի համիլտոնյանության վերաբերյալ Վանգի խնդրի մասին; О задаче Ванга о гамильтоновости двудольных орграфов

Coverage:

26-34

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.

Publisher:

Изд-во НАН РА

Date created:

2018-02-22

Format:

pdf

Identifier:

oai:arar.sci.am:258954

Location of original object:

ՀՀ ԳԱԱ Հիմնարար գիտական գրադարան