Edge reductions in cyclically \(k\)-connected cubic graphs (Q922553): Difference between revisions

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.