Wyniki wyszukiwania

Sortuj według:

Ogranicz wyniki do:

Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik

Trestles in polyhedral graphs

100%

Tkáč M., Voss H.-J.

Discussiones Mathematicae Graph Theory

2002

tom 22

nr 1

193-198

Light classes of generalized stars in polyhedral maps on surfaces

100%

Jendrol' S., Voss H.-J.

Discussiones Mathematicae Graph Theory

2004

tom 24

nr 1

85-107

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.

Ograniczanie wyników

2 Discussiones Mathematicae Graph Theory

2 Voss H.-J.

1 Jendrol' S.

1 Tkáč M.

1 2004

1 2002

Wyniki wyszukiwania

Trestles in polyhedral graphs

Light classes of generalized stars in polyhedral maps on surfaces