Home

Пятница, 25 марта, 18-00

Пятница, 25 марта, 106. Начало в 18:00.

Докладчик: С.А. Образцова.

Тема: О вершинах степени $k$ минимальных и минимальных относительно стягивания $k$-связных графов: верхние оценки..

Abstract

В статье Р. Халина был задан вопрос о том, какова наибольшая константа $c_k$, такая, что количество вершин степени $k$ в минимальном и минимальном по стягиванию $k$-связном графе $G$ равно по крайней мере $c_k|G|$. На настоящий момент для $k=4$ известна точная оценка (а именно $c_4=1$) и для $k \geq 5$ неизвестно никаких верхних оценок. В докладе будут построены серии графов, с помощью которых доказываются верхние оценки для $c_k$ при всех $k \geq 5$.