Co-author(s) :

Կարապետյան Իսկանդար ; Карапетян Искандар

Abstract:

Վանգը (Discrete Mathematics and Theoretical Computer Science, vol. 19(3) 2017) առաջարկել է հետևյալ խնդիրր: Խնդիր: Դիցուք D-ն ուժեղ կապակցված 2a-գագաթանի 2a > 8 կողնորոշված երկմասնյա հավասարակշռված գրաֆ է, որում գագաթների ցանկացած { x, yg հաղթող զույգի համար տեղի ունեն հետևյալ անհավասարությունները. d(x) > 2a — k, և d(y) > a + k կամ d(x) > a + k և d(y) > 2a — k, որտեղ 2 < k < a/2: Արդյոք D-ն համիլտոնյան է: Ներկա աշխատանքում ապացուցված է, որ եթե D գրաֆը բավարարում է Վանգի խնդրի պայմաններին, ապա (i) D գրաֆը պարունակում է ցիկլ-ֆակտոր և առնվազն չորս երկարությամբ ոչ-համիլտոնյան ցիկլ, (ii) D գրաֆի ցանկացած x գագաթի համար գոյություն ունի այնպիսի մի y գագաթ, որ { x, yg - ը հաղթող զույգ է:
; Ванг (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:

ՀՀ ԳԱԱ «ԳԻՏՈՒԹՅՈՒՆ» ՀՐԱՏԱՐԱԿՉՈՒԹՅՈՒՆ ; Издательство "Гитутюн" НАН РА

Date submitted:

20.09.2017

Date accepted:

16.01.2018

Identifier:

oai:noad.sci.am:135883

Language:

Անգլերեն ; Английский

Journal or Publication Title:

Կիբեռնետիկայի և հաշվողական տեխնիկայի մաթեմատիկական հարցեր

Affiliation:

Ինֆորմատիկայի և ավտոմատացման պրոբլեմների ինստիտուտ

Country:

Հայաստան