On minimally 3-connected graphs on a surface
type: Item
instance of: scholarly article
title: On minimally 3-connected graphs on a surface
zbMATH Open document ID: 1060.05027
author: Katsuhiro Ota
published in: AKCE International Journal of Graphs and Combinatorics
publication date: 2005-04-15T00:00:00Z
review text: \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.
reviewed by: Tomáš Madaras
Mathematics Subject Classification ID: 05C10
Mathematics Subject Classification ID: 05C35
Mathematics Subject Classification ID: 05C40
zbMATH DE Number: 2157032
zbMATH Keywords: minimally 3-connected graph
zbMATH Keywords: closed surface
zbMATH Keywords: triangulation
MaRDI profile type: Publication
description: scientific article; zbMATH DE number 2157032