2-connected spanning subgraphs with low maximum degree in locally planar graphs (Q875943)

From MaRDI portal
scientific article
Language Label Description Also known as
English
2-connected spanning subgraphs with low maximum degree in locally planar graphs
scientific article

    Statements

    2-connected spanning subgraphs with low maximum degree in locally planar graphs (English)
    0 references
    16 April 2007
    0 references
    The known result of Tutte that every 4-connected planar graph is Hamiltonian has many generalizations. In this paper, recent results of \textit{T. Böhme, B. Mohar} and \textit{C. Thomassen} [J. Comb. Theory, Ser. B 85, 338--347 (2002; Zbl 1025.05035)] and \textit{K. Kawarabayashi, A. Nakamoto} and \textit{K. Ota} [J. Comb. Theory, Ser. B 89, 207--229 (2003; Zbl 1031.05040)] are improved by proving the existence of a function \(a: \mathbb{N}_0\times\mathbb{R}_+\mapsto \mathbb{N}\) such that for each \(\varepsilon>0\), if \(G\) is a 4-connected graph embedded on a surface of Euler genus \(k\) such that the face-width of \(G\) is at least \(a(k,\varepsilon)\) then \(G\) has a 2-connected spanning subgraph with maximum degree at most 3 in which the number of vertices of degree 3 does not exceed \(\varepsilon | V(G)| \).
    0 references
    spanning subgraph
    0 references
    surface
    0 references
    embedding
    0 references
    representativity
    0 references
    degree restriction
    0 references
    4-connected graph
    0 references
    0 references
    0 references
    0 references

    Identifiers