"Записки научных семинаров ПОМИ"
Том 543, стр. 15-29
Удаление дерева из $n$-связного графа с сохранением связности
Е. Ю. Аксенова, Д. В. Карпов
Президентский
Физико-математический лицей No. 239,
ул. Кирочная, д. 8,
191028, Санкт-Петербург, Россия
elizaveta.yu.aksenova@gmail.com
С.-Петербургское
отделение Математического института
им. В А. Стеклова РАН,
Фонтанка 27, 191023 С.-Петербург, Россия
dvk0@yandex.ru
- Аннотация:
Пусть $G$ -- $n$-связный граф, а $T$ -- произвольное дерево
на $n+1$ вершине, отличное от $K_{1,n}$. Доказано, что $G$ имеет
изоморфный $T$ подграф, в результате удаления которого получается
связный граф. Доказано, что из любого трехсвязного графа можно удалить
подграф $K_{1,3}$ так что граф остается связным, а при $n \ge 4$
из любого $n$-связного графа, имеющего вершину степени более $n$,
можно удалить подграф $K_{1,n}$ так, что граф останется связным.
Показано, что при $n=4$ и $n\ge 6$ для $n$-регулярных $n$-связных
графов аналогичное утверждение неверно.
Доказано, что для любого $k\le 2n-1$ из $n$-связного графа можно
удалить путь на $k$ вершинах так, что граф останется связным.
Показано, что аналогичное утверждение для пути на $2n$ вершинах неверно.
Библ. -- 7 назв.
- Ключевые слова: вершинная связность графа, $n$-связный граф, дерево
[vertex connectivity, $n$-connected graph, tree]
Полный текст(.pdf)