Mathematical Logic and Discrete Mathematics at PDMI

Пятница, 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