RUS  ENG
Полная версия
ЖУРНАЛЫ // Записки научных семинаров ПОМИ // Архив

Зап. научн. сем. ПОМИ, 2014, том 427, страницы 41–65 (Mi znsl6042)

Эта публикация цитируется в 2 статьях

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

Д. В. Карповab

a С.-Петербургское отделение Математического института им. В. А. Стеклова РАН, Фонтанка 27, С.-Петербург
b Математико-механический факультет СПбГУ, Россия

Аннотация: Граф называется $k$-связным, если он имеет хотя бы $k+1$ вершину и остается связным при удалении любых своих $k-1$ вершин. $k$-связный граф называется минимальным, если при удалении любого его ребра граф перестает быть $k$-связным. В. Мадер доказал, что минимальный $k$-связный граф на $n$ вершинах содержит как минимум $\frac{(k-1)n+2k}{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$-связный граф.

УДК: 519.173.1

Поступило: 19.11.2014


 Англоязычная версия: Journal of Mathematical Sciences (New York), 2016, 212:6, 666–682

Реферативные базы данных:


© МИАН, 2024