Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
   
Mobile Device Pairing
Green Open Access
Transactions of the American Mathematical Society
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 Free Access

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

DOI: http://dx.doi.org/10.1090/S0002-9947-1984-0743738-4
PII: S 0002-9947(1984)0743738-4
Keywords: Graph connectivity, $ 4$-connected graphs, structure
Article copyright: © Copyright 1984 American Mathematical Society