Laboratory of Mathematical Logic at PDMI

Пятница, 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$. Тем самым, все доказанные оценки - точны.