Splitting and contractible edges in 4-connected graphs
Let \(G\) be a graph and \(x\) a vertex of degree four with \(N_G(x)=\{a,b,c,d\}\). The operation of deleting \(x\) and adding the edges \(ab\) and \(cd\) is called splitting at \(x\). An edge \(e\) of a graph \(G\) is said to be \(k\)-contractible if contraction of \(e\) yields a \(k\)-connected graph. Splitting has been studied as a reduction method to preserve edge-connectivity. This paper considers splitting and \(4\)-contractible edges as tools for reduction of \(4\)-connected graphs, and proves that for a \(4\)-connected graph \(G\) of order at least six, there exists either a \(4\)-contractible edge or a vertex eligible for splitting preserving \(4\)-connectedness near every vertex in \(G\).
- Contractible edges in a 4-connected graph with vertices of degree greater than four
- Edges incident with a vertex of degree greater than four and a lower bound on the number of contractible edges in a 4-connected graph
- A constructive characterization of 4-connected graphs
- scientific article; zbMATH DE number 1530019
- Reduction for 3-connected graphs of minimum degree at least four
- A recursive characterization of the 4-connected graphs
- A Reduction Method for Edge-Connectivity in Graphs
- A survey on contractible edges in graphs of a prescribed vertex connectivity
- Contractible edges in 3-connected graphs
- Cyclic coloration of 3-polytopes
- Generalizaions of critical connectivity of graphs
- scientific article; zbMATH DE number 3166039 (Why is no real title available?)
- scientific article; zbMATH DE number 1055145 (Why is no real title available?)
- scientific article; zbMATH DE number 871184 (Why is no real title available?)
- Kuratowski's theorem
- Some remarks on Arc‐connectivity, vertex splitting, and orientation in graphs and digraphs
- Uncontractable 4-connected graphs
- Untersuchungen über minimale \(n\)-fach zusammenhängende Graphen
- Splitter theorems for 4-regular graphs
- A constructive characterization of 4-connected graphs
- Reduction for 3-connected graphs of minimum degree at least four
- Contractible edges and liftable vertices in a 4-connected graph
- scientific article; zbMATH DE number 2108137 (Why is no real title available?)
- A characterization of weakly four‐connected graphs
This page was built for publication: Splitting and contractible edges in 4-connected graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1400957)
