zbMATH — the first resource for mathematics

The number of removable edges in 3-connected graphs. (English) Zbl 0931.05044
Summary: An edge of a 3-connected graph \(G\) is said to be removable if \(G-e\) is a subdivision of a 3-connected graph. D. A. Holton, B. Jackson, A. Saito and N. C. Wormald [J. Graph Theory 14, No. 4, 465-473 (1990; Zbl 0729.05037)] proved that every 3-connected graph of order at least five has at least \(\lceil(|G|+ 10)/6\rceil\) removable edges. We prove that every 3-connected graph of order at least five, except the wheels \(W_5\) and \(W_6\), has at least \((3|G|+ 18)/7\) removable edges. We also characterize the graphs with \((3|G|+ 18)/7\) removable edges. \(\copyright\) Academic Press.

05C40 Connectivity
05C75 Structural characterization of families of graphs
Full Text: DOI
[1] Bondy, J.A.; Murty, U.S.R., Graph theory with application, (1981), North-Holland New York · Zbl 1134.05001
[2] Fouquet, J.L.; Thuiller, H., K-minimal 3-connected cubic graphs, Ars combin., 26, 149-190, (1988) · Zbl 0704.05025
[3] Holton, D.A.; Jackson, B.; Saito, A.; Wormald, N.C., Removable edges in 3-connected graphs, J. graph theory, 14, 465-475, (1990) · Zbl 0729.05037
[4] McCuaig, W., Edge reductions in cyclically k-connected cubic graphs, J. combin. theory ser. B, 56, 16-44, (1992) · Zbl 0711.05030
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.