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