Edge reductions in cyclically \(k\)-connected cubic graphs
type: Item
instance of: scholarly article
title: Edge reductions in cyclically \(k\)-connected cubic graphs
zbMATH Open document ID: 0711.05030
DOI: 10.1016/0095-8956(92)90004-H
published in: Journal of Combinatorial Theory. Series B
publication date: 1992-01-01T00:00:00Z
review text: Let \(xy\) be an edge of a cubic graph \(G\). The graph obtained from \(G-xy\) by contracting an edge incident with each of \(x\) and \(y\) is said to be obtained from G by reduction at \(xy\). If \(G\) is cyclically \(k\)-connected, then the set of edges whose reduction gives a cubic graph which is not cyclically \(k\)-connected is denoted by \(N_ k(G)\). With the exception of three graphs, \(N_ k(G)\) consists of the edges in independent \(k\)-edge cuts. For every \(k\), we prove that \(G[N_ k]\) is a forest with at least \(k\) trees if \(G\) is a cyclically \(k\)-connected cubic graph with girth at least \(k+1\) and \(N_ k\neq \emptyset\). Other results on the structure of \(G[N_ k]\) are proven for \(k\) in \(\{3,4,5\}\). Let \(f_ k(\nu)\) be the smallest integer such that \(| N_ k(G)| \leq f_ k(\nu)\) for all cyclically \(k\)-connected cubic graphs \(G\) on \(\nu\) vertices. We determine \(f_ 3\), \(f_ 4\), and \(f_ 5\) and characterize the cyclically 5-connected cubic graphs with no edge reductions.
Mathematics Subject Classification ID: 05C40
Mathematics Subject Classification ID: 05C35
zbMATH DE Number: 4168711
zbMATH Keywords: cyclic connectivity
zbMATH Keywords: edge reduction
zbMATH Keywords: extremal
zbMATH Keywords: k-connected cubic graph
author: William McCuaig
MaRDI profile type: Publication
cites work: Q5589866
cites work: On generating planar graphs
cites work: Q3852212
cites work: Q3097395
cites work: A Generation Procedure for the Simple 3-Polytopes With Cyclically 5-Connected Graphs
cites work: Q4091985
cites work: Q3734436
cites work: Decomposition of 3-connected cubic graphs
cites work: Construction of class two graphs with maximum vertex degree three
cites work: Q3981357
cites work: Infinite Families of Nontrivial Trivalent Graphs Which are Not Tait Colorable
cites work: Q5597451
cites work: Q5530472
cites work: Q3880849
cites work: Ecken vom Grad \(n\) in minimalen \(n\)-fach zusammenhängenden Graphen
cites work: The maximum genus of vertex-transitive graphs
cites work: Q4089424
cites work: On Hamiltonian Circuits
cites work: A non-Hamiltonian planar graph
cites work: Q5508780
cites work: Q3048871
full work available at URL: 0095-8956(92)90004-h
OpenAlex ID: W2038044706
Recommended article: Cycles through edges in cyclically \(k\)-connected cubic graphs
Recommended article: Algorithm Theory - SWAT 2004
Recommended article: Uniform cyclic edge connectivity in cubic graphs
Recommended article: A polynomial algorithm for cyclic edge connectivity of cubic graphs
Recommended article: Q3414887
Recommended article: Cycles in cube-connected cycles graphs
Recommended article: Q3760576
Recommended article: On the number of cycles in 3-connected cubic graphs
Recommended article: Vertex-edge domination in cubic graphs
description: scientific article; zbMATH DE number 4168711