"Записки научных семинаров ПОМИ"

Том 391, стр. 157-197

Nanyang Technological University, Singapore

svetlana.obraztsova@gmail.com

Аннотация: Р. Халин в своей статье (в ``Recent Progress in Combinatorics'', Academic Press, 1969) сформулировал задача о нахождении наибольшей константы $c_k$, такой, что количество вершин степени $k$ в минимальном и минимальном по стягиванию $k$-связном графе $G$ равно по крайней мере $c_k|G|$. Двадцатью годами позже Н.\,Мартиновым и, независимо, М.\,Фонтэ была найдена константа $c_4$ ($c_4=1$). В этой статье изучается локальная структура минимального и минимального по стягиванию $k$-связного графа и доказывается, что $c_k \geq \frac{1}{2}$ (для $k=9,10$). Этот результат продлевает последовательность $c_k$, для которых доказана нижняя оценка $\frac{1}{2}$ до $k=6,7,8,9,10$. Библ. -- 18 назв.
Ключевые слова:$k$-связность, минимальный $k$-связный, минимальный по стягиванию $k$-связный, нижние оценки [k-connectivity, minimally k-connected, contraction critically k-connected, lower bounds]