Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)



Minimal cyclic-$ 4$-connected graphs

Author: Neil Robertson
Journal: Trans. Amer. Math. Soc. 284 (1984), 665-687
MSC: Primary 05C35; Secondary 05C40
MathSciNet review: 743738
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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 $ \vert E(G)\vert$ can be carried out effectively within the class.

References [Enhancements On Off] (What's this?)

Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC: 05C35, 05C40

Retrieve articles in all journals with MSC: 05C35, 05C40

Additional Information

Keywords: Graph connectivity, $ 4$-connected graphs, structure
Article copyright: © Copyright 1984 American Mathematical Society

American Mathematical Society