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
    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
    0 references
    4-connected graphs
    0 references
    contraction
    0 references
    splitting
    0 references

    Identifiers