Subgraphs with Restricted Degrees of their Vertices in Large Polyhedral Maps on Compact Two-manifolds |
| |
| Authors: | S Jendrol&#x; H -J Voss |
| |
| Institution: | a Department of Geometry and Algebra, P. J. 
afárik University and Institute of Mathematics, Slovak Academy of Sciences, Jesenná 5, 041 54, Ko
ice, Slovakia;b Department of Algebra, Technical University Dresden, Mommsenstrasse 13, D–01062, Dresden, Germany |
| |
| Abstract: | 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 onM , which has at least (8 k2 + 6 k − 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 4 k + 4. Moreover, we show that the bound 4k + 4 is best possible. Fabrici and Jendrol’ proved that for the sphere this bound is 10 ifk = 2 and 4 k + 3 if k ≥ 3. We also show that the same holds for the projective plane. |
| |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
