Spanning trees in locally planar triangulations (Q1333338): Difference between revisions
From MaRDI portal
Changed an Item |
Set profile property. |
||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank |
Revision as of 03:58, 5 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Spanning trees in locally planar triangulations |
scientific article |
Statements
Spanning trees in locally planar triangulations (English)
0 references
1 December 1994
0 references
Thomassen has recently shown that a triangulation of the orientable surface of genus \(g\) has a spanning tree of maximum degree at most 4, provided every noncontractible cycle has length at least \(2^{3g+4}\). We show that a 4-connected triangulation of the orientable surface of genus \(g\) has a spanning tree of maximum degree at most 3, provided that every noncontractible cycle has length at least \(2^{3g+5}\). This proves a result suggested by Thomassen. Examples demonstrate that some condition on the length of the noncontractible cycles is necessary for a result of this kind.
0 references
triangulation
0 references
orientable surface
0 references
spanning tree
0 references
noncontractible cycle
0 references