Light Paths in Large Polyhedral Maps with Prescribed Minimum Degree

• Published in: Electronic notes in discrete mathematics 2002-07, Vol.11, p.386-409
• Main Authors: Jendrol, S., Voss, H.-J.
• Format: Article
• Language: English
• Subjects: compact 2-manifold embeddings of graphs; light graph; path; Subgraphs with bounded degrees
• ISSN: 1571-0653; 1571-0653
• DOI: 10.1016/S1571-0653(04)00083-6

Let k be an integer and M be a closed 2-manifold with Euler characteristic χ ( M) ≤ 0 . We prove that each polyhedral map G on M with minimum degree δ and large number of vertices contains a k-path P, a path on k vertices, such that: (i) for δ ≥ 4 every vertex of P has, in G, degree bounded from above by 6 k − 12, k ≥ 8 (It is also shown that this bound is tight for k even and that for k odd this bound cannot be lowered below 6 k − 14); (ii) for δ ≥ 5 and k ≥ 68 every vertex of P has, in G, a degree bounded from above by 6 k − 2 log 2 k + 2 (For every k ≥ 68 and for every M we construct a large polyhedral map such that each k-path in it has a vertex of degree at least 6 k − 72 log 2 ( k−1) + 112.); (iii) (The authors have proved in their previous papers that) for δ = 3 every vertex of P has, in G, a degree bounded from above by 6k if k = 1 or k even, and by 6 k − 2 if k ≥ 3, k odd; these bounds are sharp. The paper also surveys previous results in this field.