# Cyclically five-connected cubic graphs

## Author(s): Robertson, Neil; Seymour, Paul D.; Thomas, Robin

To refer to this page use: http://arks.princeton.edu/ark:/88435/pr1fx0f
DC FieldValueLanguage
dc.contributor.authorRobertson, Neil-
dc.contributor.authorSeymour, Paul D.-
dc.contributor.authorThomas, Robin-
dc.date.accessioned2018-07-20T15:10:38Z-
dc.date.available2018-07-20T15:10:38Z-
dc.date.issued2017-07en_US
dc.identifier.citationRobertson, Neil, Seymour, PD, Thomas, Robin. (2017). Cyclically five-connected cubic graphs. JOURNAL OF COMBINATORIAL THEORY SERIES B, 125 (132 - 167. doi:10.1016/j.jctb.2017.03.003en_US
dc.identifier.issn0095-8956-
dc.identifier.urihttp://arks.princeton.edu/ark:/88435/pr1fx0f-
dc.description.abstractA 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 G\textbackslashF 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’ such that H topologically contains G’ and G’ is obtained from G in one of the following two ways. Either G’ is obtained from G by subdividing two distinct edges of G and joining the two new vertices by an edge, or G’ 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’ 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’ is required to be cyclically 5-connected. However, in this more general setting the operations describing the possible graphs G’ are more complicated. (C) 2017 Published by Elsevier Inc.en_US
dc.format.extent132 - 167en_US
dc.language.isoen_USen_US
dc.relation.ispartofJOURNAL OF COMBINATORIAL THEORY SERIES Ben_US
dc.rightsAuthor's manuscripten_US
dc.titleCyclically five-connected cubic graphsen_US
dc.typeJournal Articleen_US
dc.identifier.doidoi:10.1016/j.jctb.2017.03.003-
dc.date.eissued2017-03-31en_US
dc.identifier.eissn1096-0902-
pu.type.symplectichttp://www.symplectic.co.uk/publications/atom-terms/1.0/journal-articleen_US

Files in This Item:
File Description SizeFormat