Title:

Երկար ցիկլեր 1-ից մեծ կոշտություն ունեցող գրաֆներում ; Длинные циклы в t-жестких графах при t > і

Author:

Նիկողոսյան ժորա ; Никогосян Жора

Type:

Հոդված

Uncontrolled Keywords:

համիլտոնյան ցիկլ ; երկարագույն ցիկլ ; նվազագույն ցիկլ ; աստիճան ; կոշտություն ; гамильтоновый цикл ; окружение ; минимальный степень ; прочность

Abstract:

Ապացուցվում է, որ եթե δ նվազագույն աստիճան ունեցող n-գագաթանի գրաֆն ունի 1-ից մեծ կոշտություն, ապա այն ունի առնվազն {n,2δ+4}երկարության ցիկլ, կամ համընկնում է Պետերսենի գրաֆի հետ:
; Доказывается, что любой n-вершинный t-жесткий граф с минимальной степенью δ при t > 1 имеет цикл длины не меньше min {n,2δ+4}.

Affiliation:

Ինֆորմատիկայի և ավտոմատացման պրոբլեմների ինստիտուտ ; Институт проблем информатики и автоматизации