×

zbMATH — the first resource for mathematics

Enumeration of unrooted orientable maps of arbitrary genus by number of edges and vertices. (English) Zbl 1246.05076
Summary: A genus-\(g\) map is a 2-cell embedding of a connected graph on a closed, orientable surface of genus \(g\) without boundary, that is, a sphere with \(g\) handles. Two maps are equivalent if they are related by a homeomorphism between their embedding surfaces that takes the vertices, edges and faces of one map into the vertices, edges and faces, respectively, of the other map, and preserves the orientation of the surfaces.
A map is rooted if a dart of the map – half an edge – is distinguished as its root. Two rooted maps are equivalent if they are related by a homeomorphism that has the above properties and that also takes the root of one map into the root of the other. By counting maps, rooted or unrooted, we mean counting equivalence classes of those maps.
To count unrooted genus-\(g\) maps, we first needed to count rooted maps of every genus up to \(g\). A recursively-defined generating function for counting rooted maps of arbitrary genus by number of faces and vertices was found by D. Arquès and A. Giorgetti [J. Comb. Theory, Ser. B 77, No. 1, 1–24 (1999; Zbl 1029.05073)], and numerical values were obtained for \(g\leq 3\). The first two authors jointly extended the solution of this recursion up to g=5. Valery Liskovets used quotient maps and Tutte’s enumeration formula for rooted genus-0 maps to count unrooted genus-0 maps by number of edges. A. Mednykh and R. Nedela [J. Comb. Theory, Ser. B 96, No. 5, 706–729 (2006; Zbl 1102.05033)] generalized Liskovets’ method to count unrooted maps of genus 1, 2 and 3 by number of edges.
In this paper, we describe the above-mentioned previously-obtained results and present the following new ones. The first author wrote an optimized program in C to extend the solution of the Arquès – Giorgetti recurrence, and thus the enumeration of rooted maps by number of edges and vertices, up to \(g\)=10. The second and third authors extended the enumeration of rooted and unrooted maps by number of edges up to genus 11 using tables computed and published on a web site by Ján Karabás, a student of Nedela. Using Liskovets’ refinement of the Mednykh – Nedela method and the tables of numbers of rooted maps, the first author counted unrooted maps of genus up to 10 by number of edges and vertices.

MSC:
05C30 Enumeration in graph theory
05C85 Graph algorithms (graph-theoretic aspects)
Software:
CLN
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Arquès, D., Une relation fonctionnelle nouvelle sur LES Cartes planaires pointées, J. combin. theory ser. B, 39, 1, 27-42, (1985) · Zbl 0571.05001
[2] Arquès, D., Relations fonctionnelles et dénombrement des Cartes pointées sur le tore, J. combin. theory ser. B, 43, 3, 253-274, (1987) · Zbl 0628.05040
[3] Arquès, D.; Giorgetti, A., Énumération des Cartes pointées de genre quelconque en fonction des nombres de sommets et de faces, J. combin. theory ser. B, 77, 1, 1-24, (1999) · Zbl 1029.05073
[4] Babai, L.; Imrich, W.; Lovász, L., Finite homeomorphism groups of the 2-sphere, (), 61-75 · Zbl 0305.57029
[5] Bender, E.A.; Canfield, E.R., The asymptotic number of rooted maps on a surface, J. combin. theory ser. A, 43, 2, 244-257, (1986) · Zbl 0606.05031
[6] Bender, E.A.; Canfield, E.R., The number of rooted maps on an orientable surface, J. combin. theory ser. B, 53, 2, 293-299, (1991) · Zbl 0751.05052
[7] Bujalance, E.; Etayo, J.; Gamboa, J.; Gromadzki, G., Automorphism groups of compact bordered Klein surfaces, (1990), Springer-Verlag Berlin · Zbl 0709.14021
[8] Cori, R.; Marcus, M., Counting non-isomorphic chord diagrams, Theor. comput. sci., 204, 1-2, 55-73, (1998) · Zbl 0913.68148
[9] Coxeter, H.S.M., Regular polytopes, (1973), Dover New York · Zbl 0258.05119
[10] A. Giorgetti, MAP project release 0.3, August 2010. URL: https://sourceforge.net/projects/combi/files/map/map03.zip.
[11] A. Giorgetti, Combinatoire bijective et énumérative des cartes pointées sur une surface, Ph.D. Thesis, Université de Marne-la-Vallée, Institut Gaspard Monge, 1998.
[12] Harvey, W.J., Cyclic groups of automorphisms of a compact Riemann surface, Quart. J. math. oxf., 17, 86-97, (1966) · Zbl 0156.08901
[13] Jones, G.A.; Singerman, D., Theory of maps on orientable surfaces, Proc. lond. math. soc., 37, 273-307, (1978) · Zbl 0391.05024
[14] J. Karabás, Actions of cyclic groups over orientable surfaces, August 2010. URL: http://www.savbb.sk/ karabas/science.html#cycl.
[15] R.B. Kreckel, CLN - class Library for Numbers, August 2010. URL: http://www.ginac.de/CLN/.
[16] Liskovets, V.A., A census of nonisomorphic planar maps, (), 479-494
[17] Liskovets, V.A., Enumeration of nonisomorphic planar maps, Sel. math. sov., 4, 303-323, (1985) · Zbl 0578.05033
[18] Liskovets, V., A multivariate arithmetic function of combinatorial and topological significance, Integers, 10, 155-177, (2010) · Zbl 1230.11007
[19] Liskovets, V.A., A reductive technique for enumerating non-isomorphic planar maps, Discrete math., 156, 1-3, 197-217, (1996) · Zbl 0857.05044
[20] Mednykh, A.; Giorgetti, A., Enumeration of genus four maps by number of edges, Ars methematica contemporanea, 4, 2, 351-361, (2011) · Zbl 1237.05104
[21] Mednykh, A.; Nedela, R., Enumeration of unrooted maps of a given genus, J. combin. theory ser. B, 96, 5, 706-729, (2006) · Zbl 1102.05033
[22] Neumann, P.M., A lemma that is not burnside’s, Math. sci., 4, 133-141, (1979) · Zbl 0409.20001
[23] Tutte, W.T., A census of planar maps, Canad. J. math., 15, 249-271, (1963) · Zbl 0115.17305
[24] Tutte, W.T., On the enumeration of planar maps, Bull. amer. math. soc., 74, 64-74, (1968) · Zbl 0157.31101
[25] T.R.S. Walsh, Combinatorial enumeration of non-planar maps, Ph.D. Thesis, University of Toronto, 1971.
[26] Walsh, T.R.S., A polynomial algorithm for counting rooted toroidal maps, Ars combin., 16, 49-56, (1983) · Zbl 0553.05041
[27] Walsh, T.R.S., Efficient enumeration of sensed planar maps, Discrete math., 293, 1-3, 263-289, (2005) · Zbl 1063.05070
[28] Walsh, T.R.S., Generating nonisomorphic maps without storing them, SIAM J. algebr. discrete methods, 4, 161-178, (1983) · Zbl 0521.05034
[29] T.R.S. Walsh, A. Giorgetti, Efficient enumeration of rooted maps of a given orientable genus by number of faces and vertices (submitted for publication). · Zbl 1317.05090
[30] Walsh, T.R.S.; Lehman, A.B., Counting rooted maps by genus I, J. combin. theory ser. B, 13, 192-218, (1972) · Zbl 0228.05108
[31] Wormald, N.C., On the number of planar maps, Canad. J. math., XXXIII, 1-11, (1981) · Zbl 0408.57006
[32] Wormald, N.C., Counting unrooted planar maps, Discrete math., 36, 2, 205-225, (1981) · Zbl 0467.05034
[33] Xcode, August 2010. URL: http://developer.apple.com/technologies/tools/xcode.html.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.