Light paths with an odd number of vertices in polyhedral maps

@article{Jendroľ2000,
abstract = {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 $\mathbb \{M\}$ with Euler characteristic $\chi (\mathbb \{M\})\le 0$ contains a path $P_k$ such that each vertex of this path has, in $G$, degree $\le k\left\lfloor \frac\{5+\sqrt\{49-24 \chi (\mathbb \{M\})\}\}\{2\}\right\rfloor $. 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\} \left\lfloor \frac\{5+\sqrt\{49-24\chi (\mathbb \{M\})\}\}\{2\}\right\rfloor +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\lfloor (k-\frac\{1\}\{3\})\frac\{5+\sqrt\{49-24\chi (\mathbb \{M\})\}\}\{2\}\right\rfloor $.},
author = {Jendroľ, Stanislav, Voss, Heinz-Jürgen},
journal = {Czechoslovak Mathematical Journal},
keywords = {graphs; path; polyhedral map; embeddings; graphs; path; polyhedral map; embeddings},
language = {eng},
number = {3},
pages = {555-564},
publisher = {Institute of Mathematics, Academy of Sciences of the Czech Republic},
title = {Light paths with an odd number of vertices in polyhedral maps},
url = {http://eudml.org/doc/30584},
volume = {50},
year = {2000},
}

TY - JOUR
AU - Jendroľ, Stanislav
AU - Voss, Heinz-Jürgen
TI - Light paths with an odd number of vertices in polyhedral maps
JO - Czechoslovak Mathematical Journal
PY - 2000
PB - Institute of Mathematics, Academy of Sciences of the Czech Republic
VL - 50
IS - 3
SP - 555
EP - 564
AB - 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 $\mathbb {M}$ with Euler characteristic $\chi (\mathbb {M})\le 0$ contains a path $P_k$ such that each vertex of this path has, in $G$, degree $\le k\left\lfloor \frac{5+\sqrt{49-24 \chi (\mathbb {M})}}{2}\right\rfloor $. 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} \left\lfloor \frac{5+\sqrt{49-24\chi (\mathbb {M})}}{2}\right\rfloor +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\lfloor (k-\frac{1}{3})\frac{5+\sqrt{49-24\chi (\mathbb {M})}}{2}\right\rfloor $.
LA - eng
KW - graphs; path; polyhedral map; embeddings; graphs; path; polyhedral map; embeddings
UR - http://eudml.org/doc/30584
ER -