Пятница, 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}$ висячих вершин.
Приводится бесконечная серия примеров графов, доказывающая точность всех оценок.
Этот доклад НЕ ЯВЛЯЕТСЯ ПРОДОЛЖЕНИЕМ предыдущего доклада автора.