Minimal cyclic-$4$-connected graphs
HTML articles powered by AMS MathViewer
- by Neil Robertson PDF
- Trans. Amer. Math. Soc. 284 (1984), 665-687 Request permission
Abstract:
A theory of cyclic-connectivity is developed, matroid dual to the standard vertex-connectivity. The cyclic-$4$-connected graphs minimal under the elementary operations of single-edge deletion or contraction and removal of a trivalent vertex are classified. These turn out to belong to three simple infinite families of indecomposable graphs, or to be decomposable into constituent subgraphs which themselves belong to three simple infinite families. This is modeled after W. T. Tutte’s theorem classifying the minimal $3$-connected graphs under single-edge deletion or contraction as forming the single infinite family of "wheels." Such theorems serve two main purposes: (1) illustrating the structure of graphs in the class by isolating a type of extremal graph, and (2) by providing a set-up so that induction on $|E(G)|$ can be carried out effectively within the class.References
- Neil Robertson, Pentagon-generated trivalent graphs with girth $5$, Canadian J. Math. 23 (1971), 36–47. MR 281648, DOI 10.4153/CJM-1971-004-0
- W. T. Tutte, Connectivity in graphs, Mathematical Expositions, No. 15, University of Toronto Press, Toronto, Ont.; Oxford University Press, London, 1966. MR 0210617
- W. T. Tutte, Lectures on matroids, J. Res. Nat. Bur. Standards Sect. B 69B (1965), 1–47. MR 179781
- Hassler Whitney, Congruent Graphs and the Connectivity of Graphs, Amer. J. Math. 54 (1932), no. 1, 150–168. MR 1506881, DOI 10.2307/2371086
Additional Information
- © Copyright 1984 American Mathematical Society
- Journal: Trans. Amer. Math. Soc. 284 (1984), 665-687
- MSC: Primary 05C35; Secondary 05C40
- DOI: https://doi.org/10.1090/S0002-9947-1984-0743738-4
- MathSciNet review: 743738