Ամփոփում:

Դիցուք G-ն n գագաթանի գրաֆ է ± նվազագույն աստիճանով և ± = di < d2 < < dn աստիճանային հաջորդականությամբ: Ամենաերկար ցիկլի երկարությունը նշանակվում է c-ով, իսկ ամենաերկար շղթայի երկարությունը (գագաթների քանակը) p-ով: 1952-ին Դիրակն ապացուցեց. (1) եթե G-ն 2-կապակցված գրաֆ է, ապա c > min{n, 2dig, (2) կամայական գրաֆ, որը բավարարում է di > n պայմանին, համիլտոնյան է: Վերջերս այս արդյունքները լավացվեցին աստիճանային հաջորդականությունների լեզվով' (3) կամայական 2-կապակցված գրաֆում c > min{n, d± + d±+ i}, (4) d± + d±+i > n պայմանին բավարարող կամայական գրաֆ համիլտոնյան է (Zh.G. Nikoghosyan, Degree Sequences and Long Cycles in Graphs, ArXiv:1711.04134): Ներկա աշխատանքում բերվում են (3) և (4) թեորեմների տարբերակները դոմինանտ ցիկլերի համար: Ստացված արդյունքները լավացնելի չեն:
; Пусть G является n вершинным графом с минимальной степенью ± и степенной последовательностью ± = d1 < d2 < < dn. Длина длиннейшего цикла обозначается через с, а длина длиннейшей цепи (число её вершин) - через p. В 1952 году Дирак доказал: (1) если G является 2-связным графом, то с > min{ n, 2di}; (2) если граф удовлетворяет условию di > n, то он является гамильтоновым. Недавно эти результаты были улучшены в терминах степенных последовательностей: (3) если G является 2-связным графом, то с > min{ n , d± + d±+1}; (4) если граф удовлетворяет условию d± + d±+1 > n, то он является гамильтоновым (Zh.G. Nikoghosyan, Degree Sequences and Long Cycles in Graphs, ArXiv:1711.04134). В настоящей работе представляются версии теорем (3) и (4) для доминантных циклов. Полученные результаты неулучшаемы.

Նույնականացուցիչ:

oai:noad.sci.am:136016

Երկիր:

Հայաստան