✦ LIBER ✦
Subgraphs with Restricted Degrees of their Vertices in Large Polyhedral Maps on Compact Two-manifolds
✍ Scribed by S. Jendrol’; H.-J. Voss
- Publisher
- Elsevier Science
- Year
- 1999
- Tongue
- English
- Weight
- 276 KB
- Volume
- 20
- Category
- Article
- ISSN
- 0195-6698
No coin nor oath required. For personal study only.
✦ Synopsis
Let k ≥ 2, be an integer and M be a closed two-manifold with Euler characteristic χ(M) ≤ 0. We prove that each polyhedral map G on M, which has at least (8k 2 + 6k -6)|χ (M)| vertices, contains a connected subgraph H of order k such that every vertex of this subgraph has, in G, the degree at most 4k + 4. Moreover, we show that the bound 4k + 4 is best possible. Fabrici and Jendrol' proved that for the sphere this bound is 10 if k = 2 and 4k + 3 if k ≥ 3. We also show that the same holds for the projective plane.