A Kotzig type theorem for non-orientable surfaces

Rok, strany: 2006, 245 - 253

A. Kotzig in 1955 proved that every polyhedral map on the sphere (i.e., a $3$-connected plane graph) contains an edge with degree sum of its endvertices at most $13$; this bound being sharp. J. Ivančo in 1992 proved an analogue of Kotzig's theorem for graphs of an orientable genus $g$. In this note it is proved that every simple graph embeddable in a non-orientable surface of genus $q$ and minimum degree $≥ 3$ contains an edge $e$ with degree sum $w(e)$ of its endvertices being

$$ w(e)≤ \cases 2q+11 &if 1≤ q≤ 2 , 2q+9 &if 3≤ q≤ 5 , 2q+7 &if q≥ 6 . \endcases $$

All the above bounds are tight.

ISO 690:

Jendroľ, S., Tuhársky, M. 2006. A Kotzig type theorem for non-orientable surfaces. In Mathematica Slovaca, vol. 56, no.3, pp. 245-253. 0139-9918.

APA:

Jendroľ, S., Tuhársky, M. (2006). A Kotzig type theorem for non-orientable surfaces. Mathematica Slovaca, 56(3), 245-253. 0139-9918.