Contractible edges and contractible triangles in a 3-connected graph
type: Item
instance of: scholarly article
title: Contractible edges and contractible triangles in a 3-connected graph
zbMATH Open document ID: 1479.05174
author: Kiyoshi Ando
author: Yoshimi Egawa
published in: Graphs and Combinatorics
publication date: 2021-11-25T00:00:00Z
review text: For a 3-connected graph \(G\), an edge (resp. a triangle) of \(G\) is a 3-contractible edge (resp. a 3-contractible triangle) if the graph obtained from \(G\) by contracting it is also a 3-connected graph. Let \(E_c(G), \mathcal{T}_c(G)\) be the set of 3-contractible edges of \(G\) and the set of 3-contractible triangles of \(G\), respectively. In this paper, the authors prove that if \(G\) is a 3-connected graph of order at least 7, then \(|E_c(G)|+\frac{15}{14}|\mathcal{T}_c(G)|\geq \frac{6}{7}|V(G)|\). They also construct the extremal graphs to show the sharpness of their result.
reviewed by: Shinya Fujita
Mathematics Subject Classification ID: 05C40
Mathematics Subject Classification ID: 05C35
zbMATH DE Number: 7433381
zbMATH Keywords: 3-connected graph
zbMATH Keywords: 3-contractible edge
zbMATH Keywords: 3-contractible triangle
MaRDI profile type: Publication
full work available at URL: s00373-021-02354-1
OpenAlex ID: W3173510477
cites work: Contractible edges in 3-connected graphs
cites work: The number of vertices of degree 5 in a contraction-critically 5-connected graph
cites work: Zur Theorie der n-fach zusammenhängenden Graphen
cites work: A survey on contractible edges in graphs of a prescribed vertex connectivity
cites work: Q5294699
cites work: Q3284374
DOI: 10.1007/S00373-021-02354-1
description: scientific article; zbMATH DE number 7433381