Light paths with an odd number of vertices in polyhedral maps
Stanislav Jendrol′, H.‐J. Voss · Czechoslovak Mathematical Journal · 2000
Let P k be a path on k vertices. In an earlier paper we have proved that each polyhedral map G on any compact 2-manifold $$M$$ with Euler characteristic $$x\left( M \right) \leqslant {\text{0}}$$ contains a path P k such that each vertex of this path has, in G, degree $$\leqslant k\left[ {\frac{{5 + \sqrt {49 - 24 \times \left( M \right)} }}{2}} \right]$$ . Moreover, this bound is attained for k = 1 or k ≥ 2, k even. In this paper we prove that for each odd $$k \geqslant \frac{{\text{4}}}{{\text{3}}}\left[ {\frac{{5 + \sqrt {49 - 24 \times \left( M \right)} }}{2}} \right] + 1$$ , this bound is the best possible on infinitely many compact 2-manifolds, but on infinitely many other compact 2-manifolds the upper bound can be lowered to $$\left[ {\left( {k - \frac{{\text{1}}}{{\text{3}}}} \right)\frac{{5 + \sqrt {49 - 24 \times \left( M \right)} }}{2}} \right]$$ .