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

Зап. научн. сем. ПОМИ, 2011, том 391, страницы 157–197 (Mi znsl4572)

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

О локальной структуре 9 и 10-связных графов

С. А. Образцова

Nanyang Technological University, Singapore

Аннотация: Р. Халин в своей статье (в “Recent Progress in Combinatorics”, Academic Press, 1969) сформулировал задача о нахождении наибольшей константы $c_k$, такой, что количество вершин степени $k$ в минимальном и минимальном по стягиванию $k$-связном графе $G$ равно по крайней мере $c_k|G|$. Двадцатью годами позже Н. Мартиновым и, независимо, М. Фонтэ была найдена константа $c_4$ ($c_4=1$).
В этой статье изучается локальная структура минимального и минимального по стягиванию $k$-связного графа и доказывается, что $c_k\geq\frac12$ (для $k=9,10$). Этот результат продлевает последовательность $c_k$, для которых доказана нижняя оценка $\frac12$ до $k=6,7,8,9,10$. Библ. – 18 назв.

Ключевые слова: $k$-связность, минимальный $k$-связный, минимальный по стягиванию $k$-связный, нижние оценки.

УДК: 519.173.1

Поступило: 12.10.2011


 Англоязычная версия: Journal of Mathematical Sciences (New York), 2012, 184:5, 634–654

Реферативные базы данных:


© МИАН, 2024