Removable edges in a 5-connected graph and a construction method of 5-connected graphs (Q2477398)

From MaRDI portal
Revision as of 18:26, 27 June 2024 by ReferenceBot (talk | contribs) (‎Changed an Item)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
scientific article
Language Label Description Also known as
English
Removable edges in a 5-connected graph and a construction method of 5-connected graphs
scientific article

    Statements

    Removable edges in a 5-connected graph and a construction method of 5-connected graphs (English)
    0 references
    0 references
    0 references
    13 March 2008
    0 references
    Let \(e\) be an edge of a k-connected graph. Let \(H\) be the graph obtained from \(G\) by removing \(e\) from \(G\), and for any end vertex \(x\) of \(e\) with degree \(k-1\) in \(G-e\), delete \(x\) and then add edges between any pair of non-adjacent vertices in the neighbour set of \(x\) in \(G-e\). If \(H\) is k-connected then e is said to be a removable edge of \(G\). The authors prove that a 5-connected graph has no removable edge if and only if it is isomorphic to \(K_6\). For a k-connected graph \(G\) such that end vertices of any edge of \(G\) have at most \(k-3\) common adjacent vertices, the authors prove that \(G\) has a removable edge.
    0 references
    removable edge
    0 references
    contractible edge
    0 references
    quasi connectivity
    0 references

    Identifiers