Эта публикация цитируется в
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