IMCS/Publications/BASM/Issues/BASM n.3 (40), 2002/

The 5-cycle C5 is light in large maps of minimum degree 5 on compact 2-manifolds. (English)

Authors: 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.

S. Jendrol
Institute of Mathematics
P.J. Safarik University
Jesenna 5, 041 54 Kosice
Slovak Republic
H.-J. Voss
Institute of Algebra
University of Technology Dresden
Mommsenstrasse 13, Dresden D-01062