"Записки научных семинаров ПОМИ"
Том 518, стр. 114-123
Ограничение на
минимальную степень графа в задаче о стягиваемых множествах
Н. А. Кароль
С.-Петербургский государственный университет,
Университетская наб., д. 7-9б,
199034, Санкт-Петербург, Россия
nikolaikarol@mail.ru
- Аннотация:
Пусть $G$ -- $3$-связный граф. Множество $W \subset V(G)$ называется \textit{стягиваемым},
если $G(W)$ -- это связный граф, а $G - W$ является $2$-связным графом.
В 1994 году МакКуэйг и Ота сформулировали гипотезу, гласящую,
что для любого $k \in \mathbb{N}$ существует такое $m \in \mathbb{N}$,
что любой 3-связный граф $G$ с $v(G) \geqslant m$ имеет $k$-вершинное стягиваемое множество.
В этой статье мы доказываем, что для любого $k \geqslant 5$ утверждение гипотезы выполняется,
если $\delta(G) \geqslant \left[ \frac{2k + 1}{3} \right] + 2$.
Библ. -- 9 назв.
- Ключевые слова: связность, 3-связный граф, стягиваемый подграф
[connectivity, 3-connected graph, contractible subgraph]
Полный текст(.pdf)