Light paths with an odd number of vertices in polyhedral maps. (English) Zbl 1079.05502

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)\leq 0\) contains a path \(P_k\) such that each vertex of this path has, in \(G\), degree \(\leq k\lfloor A \rfloor \) with \(2A = 5+ \sqrt {49-24\chi (\mathbb M)}\). Moreover, this bound is attained for \(k=1\) or \(k\geq 2\), \(k\) even. In this paper we prove that for each odd \(k\geq \frac 43 \lfloor A\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 \(\lfloor (k-\frac 13)A\rfloor \).


05C10 Planar graphs; geometric and topological aspects of graph theory
05C38 Paths and cycles
52B10 Three-dimensional polytopes
Full Text: DOI EuDML


[1] I. Fabrici, S. Jendroľ: Subgraphs with restricted degrees of their vertices in planar \(3\)-connected graphs. Graphs Combin. 13 (1997), 245-250. · Zbl 0891.05025
[2] 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. · Zbl 0504.05026
[3] J. Ivančo: The weight of a graph. Ann. Discrete Math. 51 (1992), 113-116. · Zbl 0773.05066
[4] S. Jendroľ: Paths with restricted degrees of their vertices in planar graphs. Czechoslovak Math. J. 49 (124) (1999), 481-490. · Zbl 1003.05055
[5] S. Jendroľ, H.-J. Voss: A local property of polyhedral maps on compact \(2\)-dimensional manifolds. Discrete Math. 212 (2000), 111-120. · Zbl 0946.05029
[6] S. Jendroľ, H.-J. Voss: Light paths with an odd number of vertices in large polyhedral maps. Ann. Comb. 2 (1998), 313-324. · Zbl 0929.05049
[7] M. Jungerman: Ph. D. Thesis. Univ. of California. Santa Cruz, California 1974.
[8] A. Kotzig: Contribution to the theory of Eulerian polyhedra. Math. Čas. SAV (Math. Slovaca) 5 (1955), 111-113.
[9] A. Kotzig: Extremal polyhedral graphs. Ann. New York Acad. Sci. 319 (1979), 569-570.
[10] G. Ringel: Map Color Theorem. Springer-Verlag Berlin (1974). · Zbl 0287.05102
[11] J. Zaks: Extending Kotzig’s theorem. Israel J. Math. 45 (1983), 281-296. · Zbl 0524.05031
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.