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