Annals of Combinatorics 2(1998) 313-324


Light Paths with an Odd Number of Vertices in Large Polyhedral Maps

S. Jendrol and H. -J. Voss

Department of Geometry and Algebra, P.J. Šafárik University and Institute of Mathematics, Slovak Academy of Sciences, Jesenná 5, 041 54 Koš sice, Slovakia
jendrol@kosice.upjs.sk

Department of Algebra, Technical University Dresden, Mommsenstrasse 13, D--01062 Dresden, Germany
voss@math.tu-dresden.de

Received March 12, 1998

AMS Subject Classification: 05Cl0, 05C38, 52B10

Abstract. Let Pk be a path on k vertices. In this paper we prove that (1) every polyhedral map on the torus and the Klein bottle contains a path Pk such that each of its vertices has degree ≤ 6k-2 if k is odd, k≥ 3, (2) every large polyhedral map on any compact 2-manifold M with Euler characteristic Χ (M)<0 contains a path Pk such that each of its vertices has degree ≤ 6k-2 if k is odd, k≥ 3, (3) moreover, these bounds are attained. For k=1 or k even, k≥ 2, the bound is 6k which has been proved in our previous paper.

Keywords: path, polyhedral map, embeddings


Get the DVI| PS|PDF file of this abstract.

back