Home

Пятница 11 ноября, 18-00, ауд. 106

Пятница, 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} $ висячих вершин. Приводится бесконечная серия примеров графов, доказывающая точность всех оценок.

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