| Title:
|
Light paths with an odd number of vertices in polyhedral maps (English) |
| Author:
|
Jendroľ, S. |
| Author:
|
Voss, H. J. |
| Language:
|
English |
| Journal:
|
Czechoslovak Mathematical Journal |
| ISSN:
|
0011-4642 (print) |
| ISSN:
|
1572-9141 (online) |
| Volume:
|
50 |
| Issue:
|
3 |
| Year:
|
2000 |
| Pages:
|
555-564 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| Summary:
|
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 $. (English) |
| Keyword:
|
graphs |
| Keyword:
|
path |
| Keyword:
|
polyhedral map |
| Keyword:
|
embeddings |
| MSC:
|
05C10 |
| MSC:
|
05C38 |
| MSC:
|
52B10 |
| MSC:
|
52B70 |
| MSC:
|
57M15 |
| idZBL:
|
Zbl 1079.05502 |
| idMR:
|
MR1777477 |
| . |
| Date available:
|
2009-09-24T10:35:42Z |
| Last updated:
|
2020-07-03 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/127593 |
| . |
| Reference:
|
[FaJe] I. Fabrici, S. Jendroľ: Subgraphs with restricted degrees of their vertices in planar $3$-connected graphs.Graphs Combin. 13 (1997), 245–250. MR 1469824, 10.1007/BF03353001 |
| Reference:
|
[GrSh] B. Grünbaum, G. C. Shephard: Analogues for tiling of Kotzig’s theorem on minimal weights of edges.Ann. Discrete Math. 12 (1982), 129–140. MR 0806977 |
| Reference:
|
[Ivan] J. Ivančo: The weight of a graph.Ann. Discrete Math. 51 (1992), 113–116. MR 1206252, 10.1016/S0167-5060(08)70614-9 |
| Reference:
|
[Jen] S. Jendroľ: Paths with restricted degrees of their vertices in planar graphs.Czechoslovak Math. J. 49 (124) (1999), 481–490. MR 1708382, 10.1023/A:1022411100562 |
| Reference:
|
[JeVo1] S. Jendroľ, H.-J. Voss: A local property of polyhedral maps on compact $2$-dimensional manifolds.Discrete Math. 212 (2000), 111–120. MR 1748678, 10.1016/S0012-365X(99)00329-5 |
| Reference:
|
[JeVo2] S. Jendroľ, H.-J. Voss: Light paths with an odd number of vertices in large polyhedral maps.Ann. Comb. 2 (1998), 313–324. MR 1774972, 10.1007/BF01608528 |
| Reference:
|
[Jun] M. Jungerman: Ph. D. Thesis. Univ. of California.Santa Cruz, California 1974. |
| Reference:
|
[Ko1] A. Kotzig: Contribution to the theory of Eulerian polyhedra.Math. Čas. SAV (Math. Slovaca) 5 (1955), 111–113. MR 0074837 |
| Reference:
|
[Ko2] A. Kotzig: Extremal polyhedral graphs.Ann. New York Acad. Sci. 319 (1979), 569–570. |
| Reference:
|
[Rin] G. Ringel: Map Color Theorem.Springer-Verlag Berlin (1974). Zbl 0287.05102, MR 0349461 |
| Reference:
|
[Zaks] J. Zaks: Extending Kotzig’s theorem.Israel J. Math. 45 (1983), 281–296. Zbl 0524.05031, MR 0720304, 10.1007/BF02804013 |
| . |
