"Записки научных семинаров ПОМИ"
Том 391, стр. 198-210
О вершинах степени $k$ минимальных и минимальных относительно
стягивания $k$-связных графов: верхние оценки
С. А. Образцова, А. В. Пастор
Nanyang Technological University,
Singapore
svetlana.obraztsova@gmail.com
С.-Петербургское отделение
Математического института
им. В.А.Стеклова РАН, Фонтанка 27,
191023 Санкт-Петербург, Россия
pastor@pdmi.ras.ru
- Аннотация:
В статье
[4] был задан вопрос о том, какова наибольшая константа $c_k$,
такая, что количество вершин
степени $k$ в минимальном и минимальном по стягиванию
$k$-связном графе $G$ равно по крайней мере $c_k|G|$.
В настоящий момент для $k=4$ известна точная оценка
(а именно $c_4=1$) и для $k \geq 5$ неизвестно никаких верхних оценок.
В этой статье доказываются верхние оценки для $c_k$ при всех $k \geq 5$.
Библ. -- 9 назв.
- Ключевые слова:$k$-связность, минимальность, минимальность по стягиванию, верхние оценки
[k-connectivity, minimally k-connected, contraction critically k-connected, upper bounds]
Полный текст(.pdf)