On minimally 3-connected graphs on a surface (Q1772196)
From MaRDI portal
| This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: On minimally 3-connected graphs on a surface |
scientific article; zbMATH DE number 2157032
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | On minimally 3-connected graphs on a surface |
scientific article; zbMATH DE number 2157032 |
Statements
On minimally 3-connected graphs on a surface (English)
0 references
15 April 2005
0 references
\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.
0 references
minimally 3-connected graph
0 references
closed surface
0 references
triangulation
0 references