Geodesic
Light paths with an odd number of vertices in polyhedral maps
Czechoslovak Mathematical Journal, Tome 50 (2000) no. 3, pp. 555-564 Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

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 $.
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 $.
Classification : 05C10, 05C38, 52B10, 52B70, 57M15
Keywords: graphs; path; polyhedral map; embeddings 
@article{CMJ_2000_50_3_a9,
     author = {Jendro\v{l}, S. and Voss, H. J.},
     title = {Light paths with an odd number of vertices in polyhedral maps},
     journal = {Czechoslovak Mathematical Journal},
     pages = {555--564},
     year = {2000},
     volume = {50},
     number = {3},
     mrnumber = {1777477},
     zbl = {1079.05502},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/CMJ_2000_50_3_a9/}
}
TY  - JOUR
AU  - Jendroľ, S.
AU  - Voss, H. J.
TI  - Light paths with an odd number of vertices in polyhedral maps
JO  - Czechoslovak Mathematical Journal
PY  - 2000
SP  - 555
EP  - 564
VL  - 50
IS  - 3
UR  - http://geodesic.mathdoc.fr/item/CMJ_2000_50_3_a9/
LA  - en
ID  - CMJ_2000_50_3_a9
ER  - 
%0 Journal Article
%A Jendroľ, S.
%A Voss, H. J.
%T Light paths with an odd number of vertices in polyhedral maps
%J Czechoslovak Mathematical Journal
%D 2000
%P 555-564
%V 50
%N 3
%U http://geodesic.mathdoc.fr/item/CMJ_2000_50_3_a9/
%G en
%F CMJ_2000_50_3_a9
Jendroľ, S.; Voss, H. J. Light paths with an odd number of vertices in polyhedral maps. Czechoslovak Mathematical Journal, Tome 50 (2000) no. 3, pp. 555-564. http://geodesic.mathdoc.fr/item/CMJ_2000_50_3_a9/