Ապացուցվում է, որ եթե δ նվազագույն աստիճան ունեցող n-գագաթանի գրաֆն ունի 1-ից մեծ կոշտություն, ապա այն ունի առնվազն {n,2δ+4}երկարության ցիկլ, կամ համընկնում է Պետերսենի գրաֆի հետ:
;
Доказывается, что любой n-вершинный t-жесткий граф с минимальной степенью δ при t > 1 имеет цикл длины не меньше min {n,2δ+4}.
oai:noad.sci.am:136048
Ինֆորմատիկայի և ավտոմատացման պրոբլեմների ինստիտուտ ; Институт проблем информатики и автоматизации
Apr 1, 2021
Jul 30, 2020
14
https://noad.sci.am/publication/149687
Հրատարակության անուն | Ամսաթիվ |
---|---|
Zhora Nikoghosyan, Long Cycles in t-Tough Graphs with t > 1 | Apr 1, 2021 |