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