- Tytuł:
- Light classes of generalized stars in polyhedral maps on surfaces
- Autorzy:
-
Jendrol', Stanislav
Voss, Heinz-Jürgen - Powiązania:
- https://bibliotekanauki.pl/articles/744433.pdf
- Data publikacji:
- 2004
- Wydawca:
- Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
- Tematy:
-
polyhedral maps
embeddings
light subgraphs
path
star
2-dimensional manifolds
surface - Opis:
-
A generalized s-star, s ≥ 1, is a tree with a root Z of degree s; all other vertices have degree ≤ 2. $S_i$ denotes a generalized 3-star, all three maximal paths starting in Z have exactly i+1 vertices (including Z). Let be a surface of Euler characteristic χ() ≤ 0, and m():= ⎣(5 + √{49-24χ( )})/2⎦. We prove:
(1) Let k ≥ 1, d ≥ m() be integers. Each polyhedral map G on with a k-path (on k vertices) contains a k-path of maximum degree ≤ d in G or a generalized s-star T, s ≤ m(), on d + 2- m() vertices with root Z, where Z has degree ≤ k·m() and the maximum degree of T∖{Z} is ≤ d in G. Similar results are obtained for the plane and for large polyhedral maps on ..
(2) Let k and i be integers with k ≥ 3, 1 ≤ i ≤ [k/2]. If a polyhedral map G on with a large enough number of vertices contains a k-path then G contains a k-path or a 3-star $S_i$ of maximum degree ≤ 4(k+i) in G. This bound is tight. Similar results hold for plane graphs. - Źródło:
-
Discussiones Mathematicae Graph Theory; 2004, 24, 1; 85-107
2083-5892 - Pojawia się w:
- Discussiones Mathematicae Graph Theory
- Dostawca treści:
- Biblioteka Nauki
Artykuł