Light paths with an odd number of vertices in polyhedral maps期刊界 All Journals 搜尽天下杂志传播学术成果专业期刊搜索期刊信息化学术搜索

Light paths with an odd number of vertices in polyhedral maps

Authors:	S. Jendroľ H. J. Voss

Affiliation:	(1) Department of Geometry and Algebra, P. J. afárik University and Institute of Mathematics, Slovak Academy of Sciences, Jesenná 5, 041 54 Koice, Slovakia.;(2) Department of Algebra, Technical University Dresden, Mommsenstrasse 13, D-01062 Dresden, Germany.

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 with Euler characteristic contains a path P_k such that each vertex of this path has, in G, degree $leqslant kleft[ {frac{{5 + sqrt {49 - 24 times left( M right)} }}{2}} right]$ . Moreover, this bound is attained for k = 1 or k 2, k even. In this paper we prove that for each odd $k geqslant frac{{text{4}}}{{text{3}}}left[ {frac{{5 + sqrt {49 - 24 times left( M right)} }}{2}} right] + 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[ {left( {k - frac{{text{1}}}{{text{3}}}} right)frac{{5 + sqrt {49 - 24 times left( M right)} }}{2}} right]$ .

Keywords:	graphs path polyhedral map embeddings
本文献已被 SpringerLink 等数据库收录！