Contractible edges in 3-connected graphs
type: Item
instance of: scholarly article
title: Contractible edges in 3-connected graphs
zbMATH Open document ID: 0611.05037
DOI: 10.1016/0095-8956(87)90065-7
author: Kiyoshi Ando
author: Hikoe Enomoto
author: Akira Saito
published in: Journal of Combinatorial Theory. Series B
publication date: 1987-01-01T00:00:00Z
review text: An edge whose contraction results in a 3-connected graph is called a contractible edge. Using two theorems of \textit{R. Halin} [Math. Ann. 182, 175-188 (1969; Zbl 0175.505); Abh. Sem. Univ. Hamburg 33, 133-163 (1969; Zbl 0175.505)] it is easy to see that every 3-connected graph G of order least five has \(\lceil (| G| +3)/5\rceil\) or more contractible edges. The authors improved this bound to \(\lceil | G| /2\rceil\) and characterizes those 3-connected graphs which attain the equality.
Mathematics Subject Classification ID: 05C40
Mathematics Subject Classification ID: 05C35
zbMATH DE Number: 3987315
zbMATH Keywords: contractible edges
reviewed by: Michael Hager
MaRDI profile type: Publication
full work available at URL: 0095-8956(87)90065-7
OpenAlex ID: W2033985129
cites work: Q4187840
cites work: Untersuchungen über minimale \(n\)-fach zusammenhängende Graphen
cites work: Zur Theorie der n-fach zusammenhängenden Graphen
cites work: Q3880849
cites work: Q3284374
cites work: Circuits containing specified edges
description: scientific article; zbMATH DE number 3987315