On minimally 3-connected graphs on a surface (Q1772196)

From MaRDI portal





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
    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

    Identifiers

    0 references
    0 references
    0 references
    0 references