On the structure of a 3-connected graph.~ 2

D. V. Karpov

Zapiski Nauchnykh Seminarov POMI, Combinatorics and graph theory. Part X, Tome 475 (2018), pp. 41-92

Résumé

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.