Light paths with an odd number of vertices in polyhedral maps

Title:

Light paths with an odd number of vertices in polyhedral maps

Creator:

Jendroĺ, Stanislav and Voss, Heinz-Jürgen

Identifier:

https://cdk.lib.cas.cz/client/handle/uuid:3bb33ded-64b9-4308-86f6-2106642e908d
uuid:3bb33ded-64b9-4308-86f6-2106642e908d

Subject:

graphs, path, polyhedral map, and embeddings

Type:

model:article and TEXT

Format:

bez média and svazek

Description:

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 $.

Language:

English

Rights:

http://creativecommons.org/publicdomain/mark/1.0/
policy:public

Coverage:

555-564

Source:

Czechoslovak Mathematical Journal | 2000 Volume:50 | Number:3

Harvested from:

CDK

Metadata only:

false