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 $.
@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/
[FaJe] I. Fabrici, S. Jendroľ: Subgraphs with restricted degrees of their vertices in planar $3$-connected graphs. Graphs Combin. 13 (1997), 245–250. | DOI | MR
[GrSh] B. Grünbaum, G. C. Shephard: Analogues for tiling of Kotzig’s theorem on minimal weights of edges. Ann. Discrete Math. 12 (1982), 129–140. | MR
[Ivan] J. Ivančo: The weight of a graph. Ann. Discrete Math. 51 (1992), 113–116. | DOI | MR
[Jen] S. Jendroľ: Paths with restricted degrees of their vertices in planar graphs. Czechoslovak Math. J. 49 (124) (1999), 481–490. | DOI | MR
[JeVo1] S. Jendroľ, H.-J. Voss: A local property of polyhedral maps on compact $2$-dimensional manifolds. Discrete Math. 212 (2000), 111–120. | DOI | MR
[JeVo2] S. Jendroľ, H.-J. Voss: Light paths with an odd number of vertices in large polyhedral maps. Ann. Comb. 2 (1998), 313–324. | DOI | MR
[Jun] M. Jungerman: Ph. D. Thesis. Univ. of California. Santa Cruz, California 1974.
[Ko1] A. Kotzig: Contribution to the theory of Eulerian polyhedra. Math. Čas. SAV (Math. Slovaca) 5 (1955), 111–113. | MR
[Ko2] A. Kotzig: Extremal polyhedral graphs. Ann. New York Acad. Sci. 319 (1979), 569–570.
[Rin] G. Ringel: Map Color Theorem. Springer-Verlag Berlin (1974). | MR | Zbl
[Zaks] J. Zaks: Extending Kotzig’s theorem. Israel J. Math. 45 (1983), 281–296. | DOI | MR | Zbl
