A Kotzig type theorem for large maps on surfaces

Rok, strany: 2003, 153 - 162

An edge $e$ of an embedded multigraph $G$ with $A$ and $B$ as endvertices is called an $(a,b)$-edge if $deg_G(A)=a$ and $deg_G(B)=b$. A. Kotzig in 1955 proved that every 3-connected planar graph $G$ contains an $(a,b)$-edge with $a+błeq 13$; the bound being tight. The goal of this paper is to prove the following theorem:

Let $G$ be a normal map on a surface $Scr M$ of Euler characteristic $χ (Scr M) łe 0$ with the number of vertices $n>26 vertχ (Scr M)vert$. Then $G$ contains an $(a,b)$-edge such that:

$$

1. a=3  and   3łe błe 12, or
2. a=4  and   4łe błe 8, or
3. 5łe a łe 6   and   5łe b łe 6.

$$

The bounds 12, 8, 6 are tight.

ISO 690:

Jendroľ, S., Tuhársky, M., Voss, H. 2003. A Kotzig type theorem for large maps on surfaces. In Tatra Mountains Mathematical Publications, vol. 27, no.3, pp. 153-162. 1210-3195.

APA:

Jendroľ, S., Tuhársky, M., Voss, H. (2003). A Kotzig type theorem for large maps on surfaces. Tatra Mountains Mathematical Publications, 27(3), 153-162. 1210-3195.