Пятница, 17 января, ауд. 203. Начало в 14:30.
Докладчик: Д.В. Карпов.
Тема: Минимальные -связные графы с минимальным числом вершин степени
.
Пусть , а
--- дерево с
. Граф
строится из
копий
дерева~
с непересекающимися множествами вершин. Для каждой вершины
обозначим через
соответствующую вершину копии
. Если
, то мы добавим
новых вершин степени
, смежных с
.
Понятно, что если , то
. Несложно проверить, что
--- минимальный экстремальный
-связный граф.
Следующая теорема --- основной результат доклада.
Теорема.
Пусть . Тогда любой экстремальный
-связный граф имеет вид
для некоторого дерева
с
.