Title:

Գրաֆում k-ավարտ կմախքային և դոմինանտ ծառերի մասին ; О k-висячих остовных и доминантных деревьях

Author:

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

Type:

Հոդված

Abstract:

Ծառի մեկ աստիճան ունեցող գագաթը կոչվում է տերև: Գրաֆում k-ից ոչ ավել տերև ունեցող ծառը կոչվում է k-ավարտ ծառ: Գրաֆում ամենամեծ k-ավարտ ծառի գագաթների քանակը նշանակվում է tk-ով: G գրաֆի T ծառը կոչվում է դոմինանտ, եթե V(G -T)ն գագաթների անկախ բազմություն է: Դիցուք, σ2-ը (σ3 -ը) գրաֆում ոչ հարևան զույգ (եռյակ) գագաթների աստիճանների հնարավոր ամենափոքր գումարն է: Քիչ տերևներով կմախքային ծառերին առնչվող ամենավաղ արդյունքը (որը ստացվել է հեղինակի կողմից 1976-ին) պնդում է' (*) եթե n գագաթանի G կապակցված գրաֆը բավարարում է σ2 > n — k + 1 պայմանին ինչ- որ մի k դրական ամբողջ թվի համար, ապա G-ն ունի k-ավարտ կմախքային ծառ: Ներկա աշխատանքում ապացուցվում է, որ ( * ) -ում կապակցվածության պայմանը կարելի է բաց թողնել: Երկրորդ արդյունքը ( * ) -ի ուժեղացումն է' n-ը փոխարինելով t k+1 -ով (ընդհանրապես tk+ 1 < n): Երրորդ արդյունքը երկրորդի տարբերակն է' դոմինանտ k-ավարտ ծառերի համար: Բերված բոլոր արդյունքները ենթակա չեն բարելավման:
; Дерево с не более чем k-висячими вершинами называется k-висячим деревом. Число верш и н максимального k-висячего дерева обозначается через tk. Через σ 2 (σ 3) обозначается минимальная сумма с тепеней двух (трех) попарно не см еж ны х вершин. Дерево T в графе G называется доминантным, если V(G-T) является н е зависимым м н оже ст вом вершин. В 1976 году д о к а зан о (автором): (*) если n вершинный связный гр аф G удовлетворяе т условию σ 2 > n — k + 1 для некоторого целого числа k, то G содержи т k-висячое о сто вн ое дерево. В насто ящей работедоказывается , что условие с вязности в (*) можно опускать. Второй результат я вляется усилением (*) с помощью замены n через tk+ 1 (напомним, что tk+ 1 < n). Приводится такж е версия второго результата для доминантных k-висячих деревьев . Все результаты неулучшаемы.