<%@ Page Language="C#" MasterPageFile="~/Main.master" AutoEventWireup="true" Title="Volume 13 Issue 3" %>
2-Cell Embeddings with Prescribed Face Lengths and Genus
Bojan Mohar
Department of Mathematics, Simon Fraser University, 8888 University Drive, Burnaby, B.C. V5A 1S6, Canada
mohar@sfu.ca
Annals of Combinatorics 14 (4) pp.525-532 December, 2010
AMS Subject Classification: 05C07, 05C10
Abstract:
Let n be a positive integer, let d1,...,dn be a sequence of positive integers, and let q=1/2∑n{i=1} di. It is shown that there exists a connected graph G on n vertices, whose degree sequence is d1,...,dn and such that G admits a 2-cell embedding in every closed surface whose Euler characteristic is at least n-q+1, if and only if q is an integer and qn-1. Moreover, the graph G can be required to be loopless if and only if diq for i=1,...,n. This, in particular, answers a question of Skopenkov.
Keywords: degree sequence, 2-cell embedding, genus, maximum genus

References:

1. Berge, C.: Graphs and Hypergraphs, 2nd. American Elsevier Publishing Co., Inc., New York (1976)

2. Bolsinov, A.V., Fomenko, A.T.: Integrable Hamiltonian Systems: Geometry, Topology, Classification. Chapman & Hall/CRC Press, Boca Raton (2004)

3. Bolsinov, A.V., Matveev, S.V., Fomenko, A.T.: Topological classification of integrable Hamiltonian systems with two degrees of freedom. Uspekhi Mat.\ Nauk 45(2), 49--77 (1990)

4. Grünbaum, B.: Convex Polytopes, 2nd. Springer-Verlag, New York (2003)

5. Lovász, L.: Combinatorial Problems and Exercises, 2nd. North-Holland, Amsterdam (1993)

6. Mohar, B., Thomassen, C.: Graphs on Surfaces. Johns Hopkins University Press, Baltimore (2001)

7. Skopenkov, A.: private communication.

8. Xuong, N.H.: How to determine the maximum genus of a graph. J. Combin. Theory Ser. B 26(2), 217--225 (1979)