Splitting and contractible edges in 4-connected graphs (Q1400957)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Splitting and contractible edges in 4-connected graphs |
scientific article |
Statements
Splitting and contractible edges in 4-connected graphs (English)
0 references
17 August 2003
0 references
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\).
0 references
4-connected graphs
0 references
contraction
0 references
splitting
0 references
0 references