Home

Пятница 17-ое января, 14-30, 203 ауд.

Пятница, 17 января, ауд. 203. Начало в 14:30.

Докладчик: Д.В. Карпов.

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

Abstract

Вершинно $ k $-связный граф называется {\it минимальным}, если он теряет $ k $-связность при удалении любого ребра. Пусть $ v(G) $ --- это количество вершин, а $ v_k(G) $ --- это количество вершин степени $ k $ в графе $ G $. Через $ \Delta(G) $ обозначается максимальная степень вершины графа $ G $. Очевидно, степени всех вершин $ k $-связного графа не менее $ k $. В 1979 году В. Мадер доказал, что $ v_k(G)\ge {(k-1)v(G)+2k\over 2k-1} (*) $ для минимального $ k $-связного графа $ G $. Эта оценка точна для любого $ k\ge 2 $. Минимальный $ k $-связный граф назовем {\em экстремальным}, если для него неравенство $ (*) $ обращается в равенство. В 1982 году Оксли описал алгоритм построения всех минимальных двусвязных и трёхсвязных графов.

Пусть $ k\ge 2 $, а $ T $ --- дерево с $ \Delta(T)\le k+1 $. Граф $ G_{k,T} $ строится из $ k $ копий $ T_1,\dots, T_k $ дерева~$ T $ с непересекающимися множествами вершин. Для каждой вершины $ a\in V(T) $ обозначим через $ a_i $ соответствующую вершину копии $ T_i $. Если $ d_G(a)=j $, то мы добавим $ k+1-j $ новых вершин степени $ k $, смежных с $ \{a_1,\dots, a_k\} $.

Понятно, что если $ v(T)=n $, то $ v(G_{k,T})=(2k-1)n+2 $. Несложно проверить, что $ G_{k,T} $ --- минимальный экстремальный $ k $-связный граф. Следующая теорема --- основной результат доклада.

Теорема. Пусть $ k\in \{3,4,5\} $. Тогда любой экстремальный $ k $-связный граф имеет вид $ G_{k,T} $ для некоторого дерева $ T $ с $ \Delta(T)\le k+1 $.