Decomposition of 3-connected cubic graphs

DOI10.1016/0012-365X(93)90365-ZMaRDI QIDQ685673zbMATH OpenFDO

Authors Jean-Luc Fouquet, Henri Thuillier

Publication date 24 October 1993

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0012-365X(93)90365-Z

zbMATH Keywords

cubic graphdecomposition

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Extremal problems in graph theory (05C35) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

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.

Recommendations

• Decomposition of 3-connected graphs
• Decomposing planar cubic graphs
• Minimum path decompositions of oriented cubic graphs
• Decomposing plane cubic graphs
• Decomposition of cubic graphs with cyclic connectivity 5

Cites work

• A Combinatorial Decomposition Theory
• Classification and enumeration of minimum (d, 3, 3)-graphs for odd d
• Construction properties of combinatorial deltahedra
• Decomposition of submodular functions
• Deltahedra are realizable as simplicial convex polyhedra
• scientific article; zbMATH DE number 3166039 (Why is no real title available?)
• scientific article; zbMATH DE number 3966114 (Why is no real title available?)
• Minimum graphs of specified diameter, connectivity and valence. II
• The minimum-order three-connected cubic graphs with specified diameters

Cited in

(16)

• The spectrum problem for the connected cubic graphs of order 10
• Counterexamples to Thomassen's conjecture on decomposition of cubic graphs
• Decomposition of cubic graphs with cyclic connectivity 5
• Decomposition of 3-connected graphs
• Decomposition of a 2-connected graph into three connected subgraphs
• scientific article; zbMATH DE number 3974987 (Why is no real title available?)
• Minimum path decompositions of oriented cubic graphs
• scientific article; zbMATH DE number 2165735 (Why is no real title available?)
• scientific article; zbMATH DE number 2094440 (Why is no real title available?)
• The spectrum problem for 3 of the cubic graphs of order 10
• scientific article; zbMATH DE number 6303054 (Why is no real title available?)
• Splitter Theorems for Cubic Graphs
• Cubic graphs with colouring defect 3
• Feynman symmetries of the Martin and c₂ invariants of regular graphs
• Splitting cubic circle graphs
• Edge reductions in cyclically \(k\)-connected cubic graphs

This page was built for publication: Decomposition of 3-connected cubic graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q685673)