Email this article On the Decomposition of a 3-Connected Graph into Cyclically 4-Edge-Connected Components
- Authors: Pastor A.V.1
-
Affiliations:
- St.Petersburg Department of Steklov Institute of Mathematics and Peter the Great St.Petersburg Polytechnic University
- Issue: Vol 232, No 1 (2018)
- Pages: 61-83
- Section: Article
- URL: https://ogarev-online.ru/1072-3374/article/view/241263
- DOI: https://doi.org/10.1007/s10958-018-3859-0
- ID: 241263
Cite item
Open Access
Access granted
Subscription Access
Abstract
A graph is called cyclically 4-edge-connected if removing any three edges from it results in a graph in which at most one connected component contains a cycle. A 3-connected graph is 4-edge-connected if and only if removing any three edges from it results in either a connected graph or a graph with exactly two connected components one of which is a single-vertex one. We show how to associate with any 3-connected graph a tree of components such that every component is a 3-connected and cyclically 4-edge-connected graph.
About the authors
A. V. Pastor
St.Petersburg Department of Steklov Institute of Mathematics and Peter the Great St.Petersburg Polytechnic University
Author for correspondence.
Email: pastor@pdmi.ras.ru
Russian Federation, St.Petersburg
Supplementary files
