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 $.