|
Zapiski Nauchnykh Seminarov 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.
Received: 29.11.2018
Citation:
D. V. Karpov, “On the structure of a 3-connected graph. 2”, Combinatorics and graph theory. Part X, Zap. Nauchn. Sem. POMI, 475, POMI, St. Petersburg, 2018, 41–92
Linking options:
https://www.mathnet.ru/eng/znsl6685 https://www.mathnet.ru/eng/znsl/v475/p41
|
|