Removable edges in cyclically 4-edge-connected cubic graphs
type: Item
instance of: scholarly article
title: Removable edges in cyclically 4-edge-connected cubic graphs
zbMATH Open document ID: 0643.05046
DOI: 10.1007/BF01864149
author: Lars Døvling Andersen
author: Herbert Fleischner
author: Bill Jackson
published in: Graphs and Combinatorics
publication date: 1988-01-01T00:00:00Z
review text: \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.
Mathematics Subject Classification ID: 05C40
Mathematics Subject Classification ID: 05C38
zbMATH DE Number: 4047768
zbMATH Keywords: cyclic edge connectivity
zbMATH Keywords: cubic graph
reviewed by: Michael Hager
MaRDI profile type: Publication
cites work: Contractible edges in 3-connected graphs
cites work: Contractible edges in \(n\)-connected graphs with minimum degree greater than or equal to \([5n/4]\)
cites work: Contractible edges in triangle-free graphs
cites work: Q4166780
cites work: Q3734436
cites work: Q3487381
description: scientific article; zbMATH DE number 4047768