Abstract:

Դիցուք C-ն G գրաֆի ամենաերկար ցիկլն է, K-ն' կապակցվածության բնութագրիչը, իսկ p-ն' G-C-ի ամենաերկար շղթայի երկարությունը: Համիլտոնյան գրաֆների տեսության առավել հայտնի հիմնարար արդյունքները' ստացված Դիրակի, Օրեի, Նեշ-Վիլյամսի, Բոնդիի, Յունգի և այլոց կողմից, իրենցից ներկայացնում են C ցիկլի երկարության գնահատականներ' արտահայտված գրաֆի գագաթների նվազագույն աստիճանով կամ աստիճանային գումարներով և •, p բնութագրիչների մասնավոր արժեքներով, երբ • < 3 և p < 1 (p = —1 դեպքը համարժեք է V (G — C) = 0 պայմանին, և C-ն կոչվում է համիլտոնյան ցիկլ; իսկ p =0 դեպքում V (G—C)-ն գագաթների անկախ բազմություն է, և C-ն կոչվում է դոմինանտ ցիկլ): Բոնդիի (1980) և Յունգի (2001) ընդհանրացված վարկածները հիմնվում են աստիճանային գումարների վրա, որտեղ p -ն և ռ-ն հանդես են գափս որպես ընդհանրական պարամետրեր' ընդգրկելով վերոհիշյալ արդյունքները որպես մասնավոր դեպքեր: Այս վարկածները ընդհանուր դեպքում մնում են չլուծված: 2009-ին հեղինակի կողմից լուծվել են Բոնդիի և Յունգի վարկածների նվազագույն աստիճանային c— տարբերակները, որտեղ С- ն ներկայացնում է V(G — C)-ի ամենաերկար ցիկլի երկարությունը (Discrete Math, v.309, 2009, 1925-1930): Հիմնվելով հեղինակի մեկ այլ աշխատանքի վրա (Graphs and Combinatorics, v.29, 2013, 15311541), ներկա աշխատանքում ապացուցվում են մի քանի համանման արդյունքներ' ընդգրկելով Բոնդիի և Յունգի նվազագույն աստիճանային p և c տարբերակները առանց կապակցվածության պայմանի, որոնք իրենց հերթին ծնում են այս վարկածների մի քանի նոր ուժեղացված և ընդլայնված տարբերակներ: Ստացված բոլոր արդյունքները լավացնելի չեն:
; Наиболее известные фундаментальные теоремы в теории гамильтоновости графов (авторы: Дирак, Оре, Неш-Вильямс, Бонди, Юнг и т.д.) представляют различные оценки длины длиннейшего цикла C графа G в терминах минимальной степени вершин или сумм степеней, связности • и длины p длиннейшей цепи в G — C для частных случаев когда • < 3 и p < 1 (в случае p = —1 имеет место V(G — C) = и C называется гамильтоновым циклом; если p = 0 то V (G — C) является независимым множеством вершин и C называется доминантным циклом). Обобщенные гипотезы Бонди (1980) и Юнга (2001) основаны на суммах степеней, где p и • являются параметрами, включающие вышеупамянутые результаты как частные случаи. Эти гипотезы остаются нерешенными. В 2009 г автор решил С-версии гипотез Бонди и Юнга на основе минимальной степени, где С обозначает длину длиннейшего цикла в V(G—C) (Discrete Math, v.309, 2009, 1925-1930). На основе другого результата автора (Graphs and Combinatorics, v.29, 2013, 1531-1541), в работе доказывается справедливость некеторых версий гипотез Бонди и Юнга, включающие p и С-версии без условия связности, которые в свою очередь порождают новые усиленные и расширенные версии этих гипотез. Все полученные результаты неулучшаемы.

Identifier:

oai:noad.sci.am:136032