"Записки научных семинаров ПОМИ"
Том 450 , стр. 109-150
О разбиении трехсвязного графа на циклически реберно-четырехсвязные компоненты
А. В. Пастор
С.-Петербургское отделение Математического института
им. В А. Стеклова РАН, Фонтанка 27,
191023 С.-Петербург;
С.-Петербургский
политехнический университет Петра Великого
avpastor@yandex.ru
- Аннотация:
Граф называется циклически реберно-четырехсвязным, если при удалении любых трех ребер все, кроме может быть одной, компоненты связности получившегося графа не содержат циклов. Трехсвязный граф является циклически реберно-четырехсвязным тогда и только тогда, когда при удалении любых трех его ребер образуется либо связный граф, либо граф, состоящий ровно из двух компонент связности, одна из которых состоит ровно из одной вершины. В работе показано как любому трехсвязному графу можно поставить в соответствие дерево компонент, каждая из которых будет вершинно трехсвязным и циклически реберно-четырехсвязным графом.
Библ. -- 9 назв.
- Ключевые слова: связность, трёхсвязные графы, циклически реберно-четырехсвязные графы
[connectivity, $3$-connected graph, cyclically $4$-edge-connected graph]
Полный текст(.pdf)