|
Записки научных семинаров ПОМИ, 2014, том 427, страницы 41–65
(Mi znsl6042)
|
|
|
|
Эта публикация цитируется в 2 научных статьях (всего в 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$-связный граф.
Поступило: 19.11.2014
Образец цитирования:
Д. В. Карпов, “Минимальные $k$-связные графы с минимальным числом вершин степени $k$”, Комбинаторика и теория графов. VII, Зап. научн. сем. ПОМИ, 427, ПОМИ, СПб., 2014, 41–65; J. Math. Sci. (N. Y.), 212:6 (2016), 666–682
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/znsl6042 https://www.mathnet.ru/rus/znsl/v427/p41
|
Статистика просмотров: |
Страница аннотации: | 256 | PDF полного текста: | 64 | Список литературы: | 43 |
|