Contractible edges and contractible triangles in a 3-connected graph

DOI10.1007/S00373-021-02354-1MaRDI QIDQ2051887zbMATH OpenOpenAlexFDO

Authors Kiyoshi Ando, Yoshimi Egawa

Publication date 25 November 2021

Published in Graphs and Combinatorics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00373-021-02354-1

zbMATH Keywords

3-connected graph3-contractible edge3-contractible triangle

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Connectivity (05C40)

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.

Recommendations

• Contractible Edges in 3-Connected Cubic Graphs
• Contractible edges in 3-connected graphs
• The number of contractible edges in 3-connected graphs
• An extremal problem on contractible edges in 3-connected graphs
• scientific article; zbMATH DE number 4202289

Cites work

• A survey on contractible edges in graphs of a prescribed vertex connectivity
• Contractible edges in 3-connected graphs
• scientific article; zbMATH DE number 3166039 (Why is no real title available?)
• scientific article; zbMATH DE number 5174567 (Why is no real title available?)
• The number of vertices of degree 5 in a contraction-critically 5-connected graph
• Zur Theorie der n-fach zusammenhängenden Graphen

Cited in

(16)

• Contractible edges in 3-connected graphs
• The number of contractible edges in 3-connected graphs
• On 3-connected graphs with contractible edge covers of size \(k\)
• Contractible triples in 3-connected graphs
• Contractible non-edges in \(3\)-connected graphs
• A remark on the connectivity of the complement of a 3-connected graph
• Contractible edges in 3-connected graphs that preserve a minor
• On the number of contractible triples in 3-connected graphs
• An extremal problem on contractible edges in 3-connected graphs
• Properly 3-contractible edges in a minimally 3-connected graph
• scientific article; zbMATH DE number 4202289 (Why is no real title available?)
• Triangle Density and Contractibility
• scientific article; zbMATH DE number 2108141 (Why is no real title available?)
• Every DFS Tree of a 3‐Connected Graph Contains a Contractible Edge
• Contractible Edges in 3-Connected Cubic Graphs
• Contractible edges in spanning trees of 3-connected graphs

This page was built for publication: Contractible edges and contractible triangles in a 3-connected graph

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2051887)