Home

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

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

Докладчик: Д.В. Карпов.

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

Abstract

Будет доказано, что у связного графа $ G $, в котором $ s $ вершин степени 3 и $ t $ вершин степени не менее 4, существует остовное дерево, в котором не менее $ {2\over 5}t +{1\over 5}s+\alpha $ висячих вершин, где $ \alpha \ge {8\over 5} $. Более того, для всех графов, кроме трёх исключений, $ \alpha \ge 2 $. Исключение составляет единственный регулярный граф степени 4 на 6 вершинах и два регулярных графа степени 4 на 8 вершинах (в которых каждое ребро входит в треугольник).

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