Ամփոփում:

Ծ գրաֆի համար օ՜շ-ով նշանակվում է Ծ-ի ոչ հարևան գագաթների աստիճանների նվազագույն գումարը: Ծառի մեկ աստիճան ունեցող գագաթը կոչվում է կախված գագաթ, իսկ առնվազն երեք աստիճան ունեցող գագաթը* ճյուղային գագաթ: Աշխատանքում դիտարկվում են միայն (*) ո գագաթանի կապակցված գրաֆներ, որոնք բավարարում են ծ2 > ո — հ +1 պայմանին ինչ-որ մի հ բնական թվի համար: 1976-ին ապացուցվել է (հեղինակի կողմից), որ (*)-ին բավարարող կամայական գրաֆ ունի ամենաշատը հ կախված գագաթ ունեցող կմախքային ծառ: Ներկա աշխատանքում նախ ցույց է տրվում, որ (*)-ին բավարարող կամայական գրաֆ ունի կմախքային ծառ, որի կախված և ճյուղային գագաթների ընդհանուր քանակը չի գերազանցում (հ+1)-ը: Երկրորդ արդյունքը պնդում է, որ (*)-ին բավարարող կամայական գրաֆ ունի կմախքային ծառ ամենաշատը 2 (հ—1) ճյուղային գագաթներով: Ըստ երրորդ արդյունքի, (*)-ին բավարարող կամայական գրաֆ ունի կմախքային ծառ, որի ճյուղային գագաթների աստիճանների գումարը չի գերազանցում ֊ (հ — 1)-ը: Բոլոր երեք գնահատականները հասանելի են:
; Для графа С через а2 обозначается минимальная сумма степеней двух несмежных вершин. Вершина в дереве называется висячей, если имеет степень 1; и называется Яг-вершиной, если имеет степень по меньшей мере 3. В работе рассматриваются только (*) п-вершинные связные графы, удовлетворяющие условию а2 > п — к + 1 для некоторого натурального числа к. В 1976 году была доказана (автором), что произвольный граф удовлетворяющий условию (*), имеет каркас с не более чем к висячими вершинами. В настоящей работе доказывается, что всякий граф удовлетворяющий условию (*), имеет каркас, где общее число висячих и Яг-вершин не превосходит к + 1. Второй результат утверждает, что всякий граф, удовлетворяющий условию (*), имеет каркас, где число Яг-вершин не превосходит ֊ (к — 1). Третий результат утверждает, что всякий граф, удовлетворяющий условию (*), имеет каркас, где сумма степеней Яг-вершин не превосходит ֊ (к — 1). Все три оценки достигаемы.

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

oai:noad.sci.am:136052