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

Zap. Nauchn. Sem. POMI, 2018 Volume 475, Pages 41–92 (Mi znsl6685)

On the structure of a 3-connected graph. 2

D. V. Karpovab

a St. Petersburg Department of Steklov Mathematical Institute of Russian Academy of Sciences, St. Petersburg, Russia
b St. Petersburg State University, Mathematics and Mechanics Faculty, St. Petersburg, Russia

Abstract: In this paper, the structure of relative disposition of $3$-vertex cutsets in a $3$-connected graph is studied. All such cutsets are divided into structural units — complexes of flowers, of cuts, of single cutsets and trivial complexes. The decomposition of the graph by a complex of each type is described in detail.
It is proved that for any two complexes ${\mathcal C}_1$ and ${\mathcal C}_2 $ of a $3$-connected graph $G$ there is a unique part of decomposition of $G$ by ${\mathcal C}_1$, that contains ${\mathcal C}_2 $. The relative disposition of complexes is described with the help of a hypertree ${\mathcal T}(G)$ — a hypergraph, any cycle of which is a subset of a certain hyperedge. It is also proved that each nonempty part of decomposition of $G$ by the set of all its $3$-vertex cutsets is either a part of decomposition of $G$ by one of the complexes or corresponds to a hyperedge of ${\mathcal T}(G)$.
This paper can be considered as a continuation of studies begun in the joint paper by D.V. Karpov and A.V. Pastor On the structure of a $3$-connected graph published in 2011.

Key words and phrases: connectivity, $3$-connected graph, cutset.

UDC: 519.173.1

Received: 29.11.2018



© Steklov Math. Inst. of RAS, 2024