Abstract:

Մանոուսակիսը (J. of Graph Theory, vol. 16, pp. 51-59, 1992) առաջարկել է հետևյալ վարկածը: Վարկած: Դիցուք D-ն 2-ուժեղ կապակցված n-գագաթանի կողմնորոշված գրաֆ է: Եթե D-ի ցանկացած ոչ կից գագաթների ցանկացած երկու տարբեր { x, y} և {ո, v} զույգերի համար տեղի ունի հետևյալ d(x) + d(y) + d(w) + d(z) > 4n — 3 անհավասարությունը, ապա D-ն հանդիսանում է համիլտոնյան: Ներկա աշխատանքում ապացուցվել է, որ եթե D կողմնորոշված գրաֆը բավարարում է Մանոուսակիսի վարկածի պայմաններին, ապա (1). D գրաֆը պարունակում է ցիկլ-ֆակտոր; (2). Եթե D-ի ոչ կից գագաթների որևէ {x, y} զույգի համար d(x) + d(y) < 2n — 2, ապա (i) D-ն համիլտոնյան է այն և միայն այն ժամանակ, երբ D-ն պարունակում x և y գագաթներով անցնող կողմնորոշված ցիկլ; (ii) D-ն համիլտոնյան է կամ պարունակում է x (y) գագաթով անցնող n — 1 երկարության կողմնորոշված ցիկլ, որը չի անցնում y (x) գագաթով (մասնավորապես, D-ն պարունակում է առնվազն n — 1 երկարության ցիկլ) ; (3). Եթե D-ի ոչ կից գագաթների որևէ {x, y} զույգի համար d(x) + d(y) < 2n — 4, ապա ցանկացած k, 2 < k < n — 1, անբողջ թվի համար D-ն պարունակում է k երկարության կողմնորոշված ցիկլ; (4). D գրաֆի որոշակի երկարություններ (n — 5)-ից մինչև (n — 1)ունեցող կողմնորոշված ցիկլերի համար ապացուցվել են մի շարք պնդումներ:
; Пусть D является 2-сильно связным n-вершинным орграфом, в котором для любых различных пар {x,y}, {n,v} несмежных вершин имеет место d(x) + d(y) + d(w) + d(z) > 4n — 3. Тогда D является гамильтоновым. В настоящей работе доказано, что если орграф D удовлетворяет условиям гипотеза Маноуссакиса, то (1). D содержит цикл-фактор; (2). Если для некоторой пары несмежных вершин x и y имеет место d(x) + d(y) < 2n — 2, то имеют место: (i) D является гамильтоновым тогда и только тогда, когда D содержит контур проходящий через вершин x и y, (ii) D является гамильтоновым или содержит контур длины n — 1, который проходит через вершину x (y) (в частности, D содержит контур длины по крайней мере n — 1); (3). Если для некоторой пары несмежных вершин x и y имеет место d(x) + d(y) < 2n — 4, то D содержит контур любой длины k, 3 < k < n — 1;(4). Доказаны ряд свойств для контуров длины от n — 5 до n — 1.

Identifier:

oai:noad.sci.am:136051

Journal or Publication Title:

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

Affiliation:

Институт проблем информатики и автоматизации