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