Decomposition of 3-connected cubic graphs
type: Item
instance of: scholarly article
title: Decomposition of 3-connected cubic graphs
zbMATH Open document ID: 0791.05079
DOI: 10.1016/0012-365X(93)90365-Z
published in: Discrete Mathematics
publication date: 1993-10-24T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 05C10
Mathematics Subject Classification ID: 05C35
zbMATH DE Number: 423574
zbMATH Keywords: cubic graph
zbMATH Keywords: decomposition
author: Jean-Luc Fouquet
author: Henri Thuillier
reviewed by: Erich Prisner
MaRDI profile type: Publication
cites work: Decomposition of submodular functions
cites work: A Combinatorial Decomposition Theory
cites work: Minimum graphs of specified diameter, connectivity and valence. II
cites work: Construction properties of combinatorial deltahedra
cites work: Q3734436
cites work: Classification and enumeration of minimum (d, 3, 3)-graphs for odd d
cites work: Deltahedra are realizable as simplicial convex polyhedra
cites work: The minimum-order three-connected cubic graphs with specified diameters
cites work: Q3284374
description: scientific article; zbMATH DE number 423574