Jendrol S., Voss H.-J.
Let G be a graph of minimum degree delta(G) >= 5 cellularly embedded in a compact 2-manifold of Euler characteristic X < = 0. The main result of the present paper is: If G has at least 2789 |X()| vertices then it contains a cycle C*5
on 5 vertices with a diagonal such that the degree sum of vertices of C*5
is at most 32. Moreover if G has no vertex of degree 12, this bound can be improved to 31. Both bounds are tight. Slightly extended results are proved if additional properties of G are required.
Institute of Mathematics
P.J. Safarik University
Jesenna 5, 041 54 Kosice
Institute of Algebra
University of Technology Dresden
Mommsenstrasse 13, Dresden D-01062