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