Laboratory of Mathematical Logic at PDMI

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

Докладчик: Д.В. Карпов (ПОМИ РАН).

Тема: Остовные деревья с большим количеством висячих вершин: оценки через количество вершин степеней 1, 3 и 4.

Abstract

Мы докажем, что у связного графа $G$, в котором $s$ вершин степени 1 и 3 и $t$ вершин степени не менее 4, существует остовное дерево, в котором не менее ${1\over 3}t +{1\over 4}s+{3\over 2}$ висячих вершин. Приводится бесконечная серия примеров графов, доказывающая точность всех оценок.

Этот доклад НЕ ЯВЛЯЕТСЯ ПРОДОЛЖЕНИЕМ предыдущего доклада автора.