# Light paths with an odd number of vertices in polyhedral maps

Stanislav Jendroľ; Heinz-Jürgen Voss

Czechoslovak Mathematical Journal (2000)

- Volume: 50, Issue: 3, page 555-564
- ISSN: 0011-4642

## Access Full Article

top## Abstract

top## How to cite

topJendroľ, Stanislav, and Voss, Heinz-Jürgen. "Light paths with an odd number of vertices in polyhedral maps." Czechoslovak Mathematical Journal 50.3 (2000): 555-564. <http://eudml.org/doc/30584>.

@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 -

## References

top- 10.1007/BF03353001, Graphs Combin. 13 (1997), 245–250. (1997) MR1469824DOI10.1007/BF03353001
- Analogues for tiling of Kotzig’s theorem on minimal weights of edges, Ann. Discrete Math. 12 (1982), 129–140. (1982) MR0806977
- 10.1016/S0167-5060(08)70614-9, Ann. Discrete Math. 51 (1992), 113–116. (1992) MR1206252DOI10.1016/S0167-5060(08)70614-9
- 10.1023/A:1022411100562, Czechoslovak Math. J. 49 (124) (1999), 481–490. (1999) MR1708382DOI10.1023/A:1022411100562
- 10.1016/S0012-365X(99)00329-5, Discrete Math. 212 (2000), 111–120. (2000) MR1748678DOI10.1016/S0012-365X(99)00329-5
- 10.1007/BF01608528, Ann. Comb. 2 (1998), 313–324. (1998) MR1774972DOI10.1007/BF01608528
- Ph. D. Thesis. Univ. of California, Santa Cruz, California 1974.
- Contribution to the theory of Eulerian polyhedra, Math. Čas. SAV (Math. Slovaca) 5 (1955), 111–113. (1955) MR0074837
- Extremal polyhedral graphs, Ann. New York Acad. Sci. 319 (1979), 569–570. (1979)
- Map Color Theorem, Springer-Verlag Berlin (1974). (1974) Zbl0287.05102MR0349461
- 10.1007/BF02804013, Israel J. Math. 45 (1983), 281–296. (1983) Zbl0524.05031MR0720304DOI10.1007/BF02804013

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.