Back to Search
Start Over
Contractible Edges and Contractible Triangles in a 3-Connected Graph
- 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.
- Subjects :
- 0211 other engineering and technologies
021107 urban & regional planning
0102 computer and information sciences
02 engineering and technology
Edge (geometry)
01 natural sciences
Contractible space
Graph
Theoretical Computer Science
Combinatorics
010201 computation theory & mathematics
Discrete Mathematics and Combinatorics
Connectivity
Mathematics
Subjects
Details
- ISSN :
- 14355914 and 09110119
- Volume :
- 37
- Database :
- OpenAIRE
- Journal :
- Graphs and Combinatorics
- Accession number :
- edsair.doi...........cf4e4371381003a8f83d12d10afbb8b0