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

Abstract

top
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 χ ( 𝕄 ) ≤ 0 contains a path P k such that each vertex of this path has, in G , degree ≤ k 5 + 49 - 24 χ ( 𝕄 ) 2 . Moreover, this bound is attained for k = 1 or k ≥ 2 , k even. In this paper we prove that for each odd k ≥ 4 3 5 + 49 - 24 χ ( 𝕄 ) 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 - 1 3 ) 5 + 49 - 24 χ ( 𝕄 ) 2 .

How to cite

top

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

NotesEmbed ?

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.