Deprecated: $wgMWOAuthSharedUserIDs=false is deprecated, set $wgMWOAuthSharedUserIDs=true, $wgMWOAuthSharedUserSource='local' instead [Called from MediaWiki\HookContainer\HookContainer::run in /var/www/html/w/includes/HookContainer/HookContainer.php at line 135] in /var/www/html/w/includes/Debug/MWDebug.php on line 372
Removable edges in cyclically 4-edge-connected cubic graphs - MaRDI portal

Removable edges in cyclically 4-edge-connected cubic graphs (Q1101466)

From MaRDI portal





scientific article; zbMATH DE number 4047768
Language Label Description Also known as
English
Removable edges in cyclically 4-edge-connected cubic graphs
scientific article; zbMATH DE number 4047768

    Statements

    Removable edges in cyclically 4-edge-connected cubic graphs (English)
    0 references
    0 references
    0 references
    1988
    0 references
    \textit{N. C. Wormald} [Combinatorial mathematics VI, Proc. Conf., Armidale/Aust. 1978, Lect. Notes Math. 748, 199-206 (1979; Zbl 0414.05034)] showed that any cyclically 4-edge-connected cubic graph with at least 10 vertices has an edge e such that the graph obtained from G by removing e, this is deleting e and suppressing the two vertices of degree 2 created by the deletion, is also cyclically 4-edge connected. The main result of this paper is: Any cyclically 4-edge-connected cubic graph G with at least 12 vertices has at least \((| E(G)| +12)/5\) removable edges. The authors also prove that this result is best possible for the class of all cyclically 4-edge-connected cubic graphs by determining the extreme graphs.
    0 references
    cyclic edge connectivity
    0 references
    cubic graph
    0 references
    0 references

    Identifiers