Home

Пятница 21-го января, 18-00

Пятница, 21 января, ауд. 106. Начало в 18:00.

Докладчик: А.В. Банкевич и Д.В. Карпов.

Тема: Оценки количества висячих вершин в остовных деревьях.

Abstract

Будет доказано, что у связного графа $ G $, в котором $ s $ вершин степени не равной 2, существует остовное дерево с не менее чем $ {s+6\over 4} $ висячими вершинами. Пусть $ G $ --- связный граф обхвата $ g $, в котором длина наибольшей цепочки последовательно соединённых вершин степени 2 не превосходит $ k\ge 1 $. Мы докажем, что у графа $ G $ существует остовное дерево, в котором не менее $ \alpha_{g,k}(v(G)-k-2)+2 $ висячиx вершин, где $ \alpha_{g,k}= {n\over n(k+3)+1} $ при $ k<g-2 $ (где $ n= [{g+1\over2}] $) и $ \alpha_{g,k}= {g-2\over (g-1)(k+2)} $ при $ k\ge g-2 $. Будут приведены бесконечные серии примеров, показывающие точность всех доказанных оценок.