Decomposition of 3-connected cubic graphs (Q685673): Difference between revisions

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.