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