"Записки научных семинаров ПОМИ"
Том 427, стр. 41-65
Минимальные $k$-связные графы с минимальным числом вершин степени $k$
Д. В. Карпов
С.-Петербургское
отделение Математического института
им. В А. Стеклова РАН,
Фонтанка 27, С.-Петербург;
Математико-механический
факультет СПбГУ,
С.Петербург, Россия
dvk0@yandex.ru
- Аннотация:
Граф называется $k$-связным, если он имеет хотя бы $k+1$ вершину и
остается связным при удалении любых своих $k-1$ вершин. $k$-связный граф
называется минимальным, если при удалении любого его ребра граф перестает
быть $k$-связным. В.Мадер доказал, что минимальный \break
$k$-связный граф на
$n$ вершинах содержит как минимум ${(k-1)n+2k\over 2k-1}$ вершин степени
$k$. В работе доказывается, что любой минимальный $k$-связный граф,
содержащий наименьшее возможное число вершин степени$k$, имеет вид
$G_{k,T}$, где $T$ -- дерево, степени вершин которого не превосходят
$k+1$. Граф $G_{k,T}$ строится из $k$ непересекающихся копий дерева $T$.
Для каждой вешины $a$ дерева $T$ обозначим через $a_1, \dots, a_k$
соответствующие ей вершины копий. Если вершина $a$ имеет степень $j$ в
дереве $T$, то добавляются $k+1-j$ новых вершин степени$k$, смежных с
$\{a_1,\dots, a_k\}$.
Библ. -- 10 назв.
- Ключевые слова: связность, минимальный $k$-связный граф
[connectivity, minimal $k$-connected graph]
Полный текст(.pdf)