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.