ISSN:
1435-5914
Keywords:
Key words and phrases. path
;
light graph
;
compact 2-manifold
;
embeddings of graphs
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
,
Mathematics
Notes:
Abstract. We prove that each polyhedral map G on a compact 2-manifold, which has large enough vertices, contains a k-path, a path on k vertices, such that each vertex of it has, in G, degree at most 6k; this bound being best possible for k even. Moreover, if G has large enough vertices of degree 〉6k, than it contains a k-path such that each its vertex has degree, in G, at most 5k; this bound is best possible for any k.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/s003730050064
Permalink