Removable edges in cyclically 4-edge-connected cubic graphs (Q1101466): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
ReferenceBot (talk | contribs) Changed an Item |
||
(3 intermediate revisions by 2 users not shown) | |||
Property / reviewed by | |||
Property / reviewed by: Michael Hager / rank | |||
Property / reviewed by | |||
Property / reviewed by: Michael Hager / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Contractible edges in 3-connected graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Contractible edges in \(n\)-connected graphs with minimum degree greater than or equal to \([5n/4]\) / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Contractible edges in triangle-free graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4166780 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3734436 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3487381 / rank | |||
Normal rank |
Latest revision as of 16:58, 18 June 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Removable edges in cyclically 4-edge-connected cubic graphs |
scientific article |
Statements
Removable edges in cyclically 4-edge-connected cubic graphs (English)
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