On minimally 3-connected graphs on a surface
\textit{W. Mader} [Arch. Math. 23, 553-560 (1972; Zbl 0228.05119)] proved that the maximal size of a minimally 3-connected graph of order \(n \geq 7\) is \(3n-9\). In the present paper, it is proved that the maximal size of a minimally 3-connected graph embedded in a closed surface with Euler characteristic \(\chi\) is \(2n-2\) for \(\chi = 2\) and \(2n - 2\chi\) for \(\chi \leq 1\). As consequence, there is determined the maximum number of edges that can be deleted from a triangulation of a closed surface with Euler characteristic \(\chi\) without breaking 3-connectivity; also, it is proved that if \(G\) is a minimally 3-connected planar graph with \(| E(G)| = 2| V(G)| - 2\), then \(G\) is a wheel.
- Minimum 3-geodetically connected graphs
- Locally Hamiltonian graphs and minimal size of maximal graphs on a surface
- On spanning trees and walks of low maximum degree
- scientific article; zbMATH DE number 4179393 (Why is no real title available?)
- 3-edge-connected embeddings have few singular edges
- scientific article; zbMATH DE number 91007 (Why is no real title available?)
- A triangulated K3 surface with the minimum number of vertices
- Deletable edges in 3-connected graphs and their applications
- Planar graphs with no 6-wheel minor
This page was built for publication: On minimally 3-connected graphs on a surface
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1772196)
