"Записки научных семинаров ПОМИ"
Том 427, стр. 89-104
О структуре $C_3$-критических минимальных $6$-связных графов
А. В. Пастор
С.-Петербургское отделение
Математического института
им. В. А. Стеклова РАН;
Санкт-Петербургский
государственный политехнический
университет, Санкт-Петербург,Россия
pastor@pdmi.ras.ru
- Аннотация:
В работе исследуются $C_3$-критические минимальные $6$-связные графы, то есть $6$-связные графы,
которые теряют $6$-связность при удалении любого ребра и в которых любой полный подграф на не более
чем трех вершинах содержится в 6-разделяющем множестве. В работе доказано, что в таком графе более
чем ${5\over9}$ его вершин имеют степень 6.
Библ. -- 18 назв.
- Ключевые слова: $k$-связность, минимальный $k$-связный граф, $C_3$-критический
$k$-связный граф
[$k$-connectivity, minimal $k$-connected graph,
$C_3$-critical $k$-connected graph]
Полный текст(.pdf)