"Записки научных семинаров ПОМИ"
Том 464, стр. 95-111
О критических трехсвязных графах ровно с двумя вершинами степени~3. Часть 1
А. В. Пастор
С.-Петербургское отделение
Математического института
им. В А. Стеклова РАН,
Фонтанка 27, 191023 С.-Петербург;
Санкт-Петербургский политехнический университет Петра Великого
pastor@pdmi.ras.ru
- Аннотация:
Граф $G$ называется \emph{критическим трехсвязным графом}, если он трехсвязен, но для любой вершины $v\in V(G)$ граф $G-v$ не является трехсвязным. R. C. Entringer и P. J. Slater доказали, что любой критический трехсвязный граф содержит как минимум две вершины степени 3. В данной работе мы дадим описание всех таких графов, при условии, что вершины степени~3 смежны. Случай несмежных вершин степени 3 будет рассмотрен во второй части статьи, которая будет опубликована позднее.
Библ. -- 14 назв.
- Ключевые слова: связность, трёхсвязные графы, критические трехсвязные графы
[connectivity, $3$-connected graph, critically $3$-connected graph]
Полный текст(.pdf)