Decomposition of 3-connected cubic graphs (Q685673)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Decomposition of 3-connected cubic graphs |
scientific article |
Statements
Decomposition of 3-connected cubic graphs (English)
0 references
24 October 1993
0 references
A 3-connected cubic graph is called decomposable if there is some 3-edge cocycle \(L\) such that \(G \backslash L\) contains two cyclic components \(Q'\) and \(Q''\). We add one new vertex to each of them, make it adjacent to the ends of \(L\) in \(Q'\) and \(Q''\) respectively, and obtain two 3- connected cubic graphs \(G'\) and \(G''\). By applying this decomposition to \(G'\), \(G''\), and so on, we finally arrive at a set \(\{G_ 1,\dots,G_ k\}\) of indecomposable 3-connected cubic graphs. Decompositions of this kind are investigated in the present paper. It is shown that, no matter in which order one decomposes a graph \(G\), one finally arrives at the same set \(\{G_ 1,\dots,G_ k\}\). Then decompositions are applied to investigate the minimum order of cubic 3-connected graphs of given diameter.
0 references
cubic graph
0 references
decomposition
0 references