Laboratory of Mathematical Logic at PDMI

Пятница, 8 апреля, ауд. 106. Начало в 18:30.

Докладчик: А. Банкевич.

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

Abstract

В докладе будет доказано, что у связного графа G без треугольников, в котором s вершин степени, не равной 2, существует остовное дерево с не менее чем (s-2)/3 + 2 висячими вершинами. Ранее был доказан ряд аналогичных оценок при различных ограничениях на граф G: минимальную степень вершины, обхват, длину цепочки вершин степени 2. Во всех случаях, где была найдена точная оценка, она становилась точной на определённом типе примеров. В докладе будет показано, что такая же логика построения экстремальных примеров не будет работать для графов без вершин степени 2 с обхватом по крайней мере g для достаточно большого g.