Co-author(s) :

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

Abstract:

Դիցուք ո-ը նշանակում է G գրաֆի գագաթների քանակը, c-ն G-ի1 ամենաերկար ցիկլի երկարությունը, p-ն* ամենաերկար շղթայի գագաթների քանակը և 5-ն* գրաֆի նվազագույն աստիճանը: 1952-ին Դիրակը ապացուցեց, որ (i) եթե G-ն 2-կապակցված գրաֆ է, ապա c > min{n, 25}: Դիրակի 25 ներքին գնահատականը իրարից անկախ ընդլայնեցին Բոնդին (1971), Բերմոնդը և Լինիալը (1976), օգտագործելով ծ 2 (ոչ հարևան երկու գագաթների աստիճանների նվազագույն գումարը) պարամետրը, (ii) եթե G-ն 2-կապակցված գրաֆ է, ապա c > min{ ո , ծ 2 } : Ներկա աշխատանքում (i) և (ii) ընդլայնումները ավելի են ընդլայնվում* գնահատականների մեջ ներմուծելով p-ն և G գրաֆի ամենաերկար շղթայի բաղեղի երկարությունը որպես նոր պարամետրեր ո , 5, ծ 2 պարամետրերի կողքին:
; Пусть п, с, р и ± обозначают число вершин графа С , длина длиннейшего цикла, число вершин длиннейшей цепи и минимальная степень графа. В 1952 году Дирак доказал, что (1) если С является 2-связным графом, то с > т т { п, 2±}: Эту оценку независимо расширили Бонди (1971), Бермонд и Линиал (1976) с помощью параметра а 2 (минимальная сумма степеней двух не соседних вершин): (н) если С является 2-связным графом, то с > т т { п , а 2}. В настоящей работе представлены две новые расширения оценок (1) и (11) помощью параметров р и длины плюща длиннейшей цепи графа С на ряду с параметрами п, ±, а 2.

Identifier:

oai:noad.sci.am:135996

Language:

Անգլերեն