Advanced Search

A generalized s-star, s ≥ 1, is a tree with a root Z of degree s; all other vertices have degree ≤ 2. $S_i$ denotes a generalized 3-star, all three maximal paths starting in Z have exactly i+1 vertices (including Z). Let be a surface of Euler characteristic χ() ≤ 0, and m():= ⎣(5 + √49-24χ( ))/2⎦. We prove: (1) Let k ≥ 1, d ≥ m() be integers. Each polyhedral map G on with a k-path (on k vertices) contains a k-path of maximum degree ≤ d in G or a generalized s-star T, s ≤ m(), on d + 2- m() vertices...

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 $𝕄$ with Euler characteristic $\chi \left(𝕄\right)\le 0$ contains a path $P_k$ such that each vertex of this path has, in $G$, degree $\le k⌊\frac{5+\sqrt{49-24\chi \left(𝕄\right)}}{2}⌋$. Moreover, this bound is attained for $k=1$ or $k\ge 2$, $k$ even. In this paper we prove that for each odd $k\ge \frac{4}{3}⌊\frac{5+\sqrt{49-24\chi \left(𝕄\right)}}{2}⌋+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 $⌊(k-\frac{1}{3})\frac{5+\sqrt{49-24\chi \left(𝕄\right)}}{2}⌋$.