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

Зап. научн. сем. ПОМИ, 2018, том 475, страницы 22–40 (Mi znsl6684)

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

О стягиваемых 5-вершинных подграфах трёхсвязного графа

Н. Ю. Власова

С.-Петербургский государственный университет, Университетский пр. 28, Старый Петергоф, 198504 Санкт-Петербург, Россия

Аннотация: Подмножество $H$ множества вершин трехсвязного конечного графа $G$ называется стягиваемым, если граф $G(H)$ связен и граф $G-H$ двусвязен. В работе доказано, что трехсвязный граф на не менее чем $11$ вершинах с минимальной степенью вершин хотя бы $4$ имеет стягиваемое множество из $5$ вершин. Библ. — 10 назв.

Ключевые слова: связность, $3$-связный граф, стягиваемый подграф.

УДК: 519.173.1

Поступило: 12.11.2018



© МИАН, 2024