Back to Search Start Over

Contractible Edges and Contractible Triangles in a 3-Connected Graph

Authors :
Yoshimi Egawa
Kiyoshi Ando
Source :
Graphs and Combinatorics. 37:1807-1821
Publication Year :
2021
Publisher :
Springer Science and Business Media LLC, 2021.

Abstract

Let G be a 3-connected graph. An edge (a triangle) of G is said to be a 3-contractible edge (a 3-contractible triangle) if the contraction of it results in a 3-connected graph. We denote by $$E_{c}(G)$$ and $$\mathcal {T}_{c}(G)$$ the set of 3-contractible edges of G and the set of 3-contractible triangles of G, respectively. We prove that if $$|V(G)|\ge 7$$ , then $$|E_{c}(G)|+ \frac{15}{14}|\mathcal {T}_{c}(G)|\ge \frac{6}{7}|V(G)|.$$ We also determine the extremal graphs.

Details

ISSN :
14355914 and 09110119
Volume :
37
Database :
OpenAIRE
Journal :
Graphs and Combinatorics
Accession number :
edsair.doi...........cf4e4371381003a8f83d12d10afbb8b0