Cyclically five-connected cubic graphs

DOI10.1016/J.JCTB.2017.03.003zbMATH Open1362.05074arXiv1503.02298OpenAlexW3099799705MaRDI QIDQ2396896FDOQ2396896

Authors: Neil Robertson, Robin Thomas, Paul Seymour 

Publication date: 26 May 2017

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Abstract: A cubic graph $G$ is cyclically 5-connected if $G$ is simple, 3-connected, has at least 10 vertices and for every set $F$ of edges of size at most four, at most one component of $$ contains circuits. We prove that if $G$ and $H$ are cyclically 5-connected cubic graphs and $H$ topologically contains $G$, then either $G$ and $H$ are isomorphic, or (modulo well-described exceptions) there exists a cyclically 5-connected cubic graph $G^{\prime }$ such that $H$ topologically contains $G^{\prime }$ and $G^{\prime }$ is obtained from $G$ in one of the following two ways. Either $G^{\prime }$ is obtained from $G$ by subdividing two distinct edges of $G$ and joining the two new vertices by an edge, or $G^{\prime }$ is obtained from $G$ by subdividing each edge of a circuit of length five and joining the new vertices by a matching to a new circuit of length five disjoint from $G$ in such a way that the cyclic orders of the two circuits agree. We prove a companion result, where by slightly increasing the connectivity of $H$ we are able to eliminate the second construction. We also prove versions of both of these results when $G$ is almost cyclically 5-connected in the sense that it satisfies the definition except for 4-edge cuts such that one side is a circuit of length four. In this case $G^{\prime }$ is required to be almost cyclically 5-connected and to have fewer circuits of length four than $G$. In particular, if $G$ has at most one circuit of length four, then $G^{\prime }$ is required to be cyclically 5-connected. However, in this more general setting the operations describing the possible graphs $G^{\prime }$ are more complicated.

Full work available at URL: https://arxiv.org/abs/1503.02298

Recommendations

• Decomposition of cubic graphs with cyclic connectivity 5
• scientific article; zbMATH DE number 3845616
• Uniform cyclic edge connectivity in cubic graphs
• Cycles through edges in cyclically \(k\)-connected cubic graphs
• Edge reductions in cyclically \(k\)-connected cubic graphs

zbMATH Keywords

generation theoremcyclically 5-connected cubic graph

Mathematics Subject Classification ID

Connectivity (05C40)

Cites Work

• Graph theory
• The four-colour theorem
• Tutte's edge-colouring conjecture
• Three-edge-colouring doublecross cubic graphs
• Title not available (Why is that?)
• Edge reductions in cyclically \(k\)-connected cubic graphs
• Graph minors. IX: Disjoint crossed paths
• Excluded minors in cubic graphs
• Convex Representations of Graphs
• On generating planar graphs
• Uniform cyclic edge connectivity in cubic graphs
• A Generation Procedure for the Simple 3-Polytopes With Cyclically 5-Connected Graphs

Cited In (18)

• Short Cycle Covers of Cubic Graphs and Intersecting 5-Circuits
• Superposition of snarks revisited
• Construction of fullerenes and Pogorelov polytopes with 5-, 6- and one 7-gonal face
• Cyclic connectivity, edge-elimination, and the twisted Isaacs graphs
• Splitter theorems for 4-regular graphs
• Title not available (Why is that?)
• Measures of edge-uncolorability of cubic graphs
• The extremal function for Petersen minors
• Splitter Theorems for Cubic Graphs
• Cycle and Path Embedding on 5-ary N-cubes
• Characterization of cyclically-4-connected cubic graphs without \(K_{4,4}\)-minor
• Tutte's 5-flow conjecture for highly cyclically connected cubic graphs
• Decomposition of cubic graphs with cyclic connectivity 5
• Title not available (Why is that?)
• Generating internally four-connected graphs
• Avoiding 5-Circuits in 2-Factors of Cubic Graphs
• Title not available (Why is that?)
• Excluded minors in cubic graphs

This page was built for publication: Cyclically five-connected cubic graphs

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