Two local and one global properties of 3-connected graphs on compact 2-dimensional manifolds
type: Item
instance of: scholarly article
title: Two local and one global properties of 3-connected graphs on compact 2-dimensional manifolds
zbMATH Open document ID: 1059.05038
published in: Journal of Combinatorial Theory. Series B
publication date: 2005-02-09T00:00:00Z
review text: Let \({\mathcal{G}}(\mathbb{M})\) be the family of all 3-connected graphs that can be embedded in a compact 2-manifold \(\mathbb{M}\) with Euler characteristic \(\chi(\mathbb{M}) < 0\). The authors prove that each graph \(G \in {\mathcal{G}}(\mathbb{M})\) that contains a \(k\)-vertex path, \(k \geq 4\), contains also a \(k\)-vertex path \(P_k\) such that each of its vertices has in \(G\) degree at most \(2 + \lfloor (6k-6-2\varepsilon)(1 + \frac{| \chi(\mathbb{M})| }{3}) \rfloor\) (where \(\varepsilon = 0\) for \(k\) even and \(\varepsilon = 1\) for \(k\) odd), and that each graph \(G \in {\mathcal{G}}(\mathbb{M})\) on at least \(k \geq 5\) vertices contains a connected subgraph of order \(k\) such that each of its vertices has in \(G\) degree at most \(2 +\lfloor (4k-2)(1 + \frac{| \chi(\mathbb{M})| }{3})\rfloor \). Both bounds are best possible; in addition, there are also the best bounds for smaller values of \(k\) provided. As an application of these results, it is proved that every graph \(G \in {\mathcal{G}}(\mathbb{M})\) has a 2-connected spanning subgraph \(H\) such that \(\Delta(H) \leq 20 - 6\chi(\mathbb{M})\).
reviewed by: Tomáš Madaras
Mathematics Subject Classification ID: 05C10
Mathematics Subject Classification ID: 05C38
Mathematics Subject Classification ID: 52B10
zbMATH DE Number: 2132704
zbMATH Keywords: 3-connected graphs
zbMATH Keywords: embeddings
zbMATH Keywords: path
zbMATH Keywords: light subgraphs
zbMATH Keywords: spanning subgraphs
author: Stanislav Jendroľ
author: Heinz-Juergen Voss
MaRDI profile type: Publication
full work available at URL: j.jctb.2004.03.004
OpenAlex ID: W2024710548
cites work: Trees in Polyhedral Graphs
cites work: 2-connected spanning subgraphs of planar 3-connected graphs
cites work: Subgraphs with restricted degrees of their vertices in planar 3-connected graphs
cites work: Subgraphs with restricted degrees of their vertices in planar graphs
cites work: 2‐connected coverings of bounded degree in 3‐connected graphs
cites work: Analogues for Tilings of Kotzig'S Theorem on Minimal Weights of Edges
cites work: On \(3\)-connected plane graphs without triangular faces
cites work: Q4027161
cites work: Subgraphs with restricted degrees of their vertices in large polyhedral maps on compact two-manifolds
cites work: A local property of polyhedral maps on compact two-dimensional manifolds
cites work: Light paths with an odd number of vertices in polyhedral maps
cites work: Light subgraphs of multigraphs on compact 2-dimensional manifolds
cites work: Subgraphs with restricted degrees of their vertices in polyhedral maps on compact 2-manifolds
cites work: Q4410027
cites work: Face-width of embedded graphs
cites work: Wie man die geschlossenen nichtorientierbaren Flächen in möglichst wenig Dreiecke zerlegen kann
cites work: Q4773723
cites work: Q3972954
cites work: On 2-connected spanning subgraphs with low maximum degree
cites work: Q3216670
cites work: Extending Kotzig's theorem
DOI: 10.1016/J.JCTB.2004.03.004
Recommended article: On planarity of graphs in 3-manifolds
Recommended article: On the connectivity of manifold graphs
Recommended article: On the 3‐Local Profiles of Graphs
Recommended article: Two local properties of graphs
Recommended article: The structure of locally finite two-connected graphs
Recommended article: Maniflods with conullity at most two as graph manifolds
Recommended article: $N_2$-locally connected graphs and their upper embeddability
Recommended article: Notes on the complexity of 3-valent graphs in 3-manifolds
Recommended article: A local property of polyhedral maps on compact two-dimensional manifolds
Recommended article: Local properties and upper embeddability of connected multigraphs
description: scientific article; zbMATH DE number 2132704