"Записки научных семинаров ПОМИ"
Том 381, стр. 97-111
О локальной структуре 7 и 8-связных графов
С. А. Образцова, А. В. Пастор
С.-Петербургское отделение
Математического института
им. В. А. Стеклова РАН,
Фонтанка 27,
191023 Санкт-Петербург, Россия
svetlana.obraztsova@pdmi.ras.ru
pastor@pdmi.ras.ru
- Аннотация:В статье рассматриваются минимальные и минимальные по стягиванию 7 и 8-связные графы.
Для них доказываются нижние оценки на долю вершин степеней 7 или 8 соответственно,
относительно общего числа вершин. Доказано, что в обоих случаях доля вершин соответствующей
степени составляет не менее 1/2.
Библ. -- 17 назв.
- Ключевые слова: $k$-связность, минимальность, минимальность по стягиванию [k-connectivity, minimally k-connected,
contraction critically k-connected]
Полный текст(.pdf)