"Записки научных семинаров ПОМИ"
Том 518, стр. 5-93
Каждый 3-связный граф на не менее чем 13 вершинах имеет стягиваемый 5-вершинный подграф
Н. Ю. Власова
Санкт-Петербургское отделение
Математического института им. В. А. Стеклова,
Российской академии наук,
наб. р. Фонтанки 27, 191023 Санкт-Петербург, Россия
evropa2100@mail.ru
- Аннотация:
Подмножество $H$ множества вершин трехсвязного конечного графа $G$ называется {\it стягиваемым},
если граф $G(H)$ связен и граф $G-H$ двусвязен. В работе доказано,
что трехсвязный граф на не менее чем 13 вершинах имеет стягиваемое множество из 5 вершин.
При этом существует трёхсвязный граф на 12 вершинах, в котором нет стягиваемого пятивершинного множества.
Библ. -- 12 назв.
- Ключевые слова: связность, 3-связный граф, стягиваемый подграф
[connectivity, 3-connected graph, contractible subgraph]
Полный текст(.pdf)