RUS  ENG
Full version
JOURNALS // Zapiski Nauchnykh Seminarov POMI // Archive

Zap. Nauchn. Sem. POMI, 2016 Volume 450, Pages 109–150 (Mi znsl6339)

This article is cited in 4 papers

On a decomposition of a $3$-connected graph into cyclically $4$-edge-connected components

A. V. Pastorab

a St. Petersburg Department of Steklov Mathematical Institute of Russian Academy of Sciences, St. Petersburg, Russia
b Peter the Great St. Petersburg Polytechnic University, St. Petersburg, Russia

Abstract: A graph is called cyclically $4$-edge-connected if removing any three edges from it leads us to a graph, at most one connected component of which contains a cycle. $3$-connected graph is $4$-edge-connected iff removing any three edges from it leads us to either a connected graph or to a graph with exactly two connected components, one of which is a single-vertex one. We show, how to correspond for any $3$-connected graph a components tree, such that every component would be a $3$-connected and cyclically $4$-edge-connected graph.

Key words and phrases: connectivity, $3$-connected graph, cyclically $4$-edge-connected graph.

UDC: 519.173.1

Received: 18.11.2016


 English version:
Journal of Mathematical Sciences (New York), 2018, 232:1, 61–83

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024