ACTA MATHEMATICA UNIVERSITATIS COMENIANAE

Vol. 61,   1   (1992)
pp.   65-68
ON NON-SEPARATING EMBEDDINGS OF GRAPHS IN CLOSED SURFACES
M. SKOVIERA

Abstract.  A. A. Zykov [Fundamentals of Graph Theory, Nauka, Moscow, 1987] asks to determine, for a given closed surface $S$, all graphs $G$ (including disconnected ones) that admit an embedding $i\: G \hookrightarrow S$ in a closed surface $S$ leaving $S-i(G)$ connected. We anwser this question completely. For connected graphs the results can be formulated as follows: $G$ has an embedding $i\: G \hookrightarrow S$ with $S-i(G)$ connected if and only if $S$ is non-orientable and $\tilde\gamma(S) \geq \beta(G) = \vertE(G)\vert - \vertV(G)\vert + 1$, or $S$ is orientable and $\gamma(S) \geq \beta(G) - \gamma_M(G)$, where $\gamma_M(G)$ is the maximum genus of $G$.

AMS subject classification.  05C10
Keywords. 
Download:     Adobe PDF     Compressed Postscript      

Acta Mathematica Universitatis Comenianae
Institute of Applied Mathematics
Faculty of Mathematics, Physics and Informatics
Comenius University
842 48 Bratislava, Slovak Republic  
Telephone: + 421-2-60295111 Fax: + 421-2-65425882  
e-Mail: amuc@fmph.uniba.sk   Internet: www.iam.fmph.uniba.sk/amuc

© Copyright 2001, ACTA MATHEMATICA UNIVERSITATIS COMENIANAE