Uncontractable 4-connected graphs

From MaRDI portal





A graph \(G\) is cyclically \(n\)-connected if any separating edge set whose removal produces two components each of which contains a cycle contains at least \(n\) edges. \(G\) is uncontractable \(n\)-connected if the (vertex) connectivity of \(G\) is \(n\) and the contraction of any edge results in a graph of connectivity \(n-1\). Theorem. The only uncontractable 4-connected graphs are \(C_n^2\) for \(n\geq 5\) and the line graphs of the cubic cyclically 4-connected graphs.




Cited in
(61)








This page was built for publication: Uncontractable 4-connected graphs

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