×

zbMATH — the first resource for mathematics

Enumeration of \(r\)-regular maps on the torus. I: Rooted maps on the torus, the projective plane and the Klein bottle. Sensed maps on the torus. (English) Zbl 1400.05019
Summary: The work that consists of two parts is devoted to the problem of enumerating unrooted \(r\)-regular maps on the torus up to all its symmetries. We begin with enumerating near-\(r\)-regular rooted maps on the torus, the projective plane and the Klein bottle, as well as some special kinds of maps on the sphere: near-\(r\)-regular maps, maps with multiple leaves and maps with multiple root darts. For \(r = 3\) and \(r = 4\) we obtain exact analytical formulas. For larger \(r\) we derive recurrence relations. Then we enumerate \(r\)-regular maps on the torus up to homeomorphisms that preserve its orientation – so-called sensed maps. Using the concept of a quotient map on an orbifold we reduce this problem to enumeration of certain above-mentioned classes of rooted maps. For \(r = 3\) and \(r = 4\) we obtain closed-form expressions for the numbers of \(r\)-regular sensed maps by edges. All these results will be used in the second part of the work to enumerate \(r\)-regular maps on the torus up to all homeomorphisms – so-called unsensed maps.

MSC:
05A15 Exact enumeration problems, generating functions
Software:
OEIS
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Arques, 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
[2] Bender, E.; Canfield, E., The asymptotic number of rooted maps on a surface, J. Combin. Theory Ser. A, 43, 244-257, (1986) · Zbl 0606.05031
[3] Bender, E.; Canfield, E., The number of rooted maps on an orientable surface, J. Combin. Theory Ser. B, 53, 293-299, (1991) · Zbl 0751.05052
[4] Bender, E. A.; Canfield, E. R., The number of degree-restricted rooted maps on the sphere, SIAM J. Discrete Math., 7, 1, 9-15, (1994) · Zbl 0794.05048
[5] Bousquet-Mélou, M.; Jehanne, A., Polynomial equations with one catalytic variable, algebraic series and map enumeration, J. Comb. Theory Ser. B, 96, 5, 623-672, (2006) · Zbl 1099.05043
[6] Brown, W. G., Enumeration of triangulations of the disk, Proc. Lond. Math. Soc., 14, 3, 746-768, (1964) · Zbl 0134.19503
[7] Brown, W. G., Enumeration of quadrangular dissections of the disk, Canad. J. Math., 17, 302-317, (1965) · Zbl 0138.19104
[8] Brown, W. G., On the existence of square roots in certain rings of power series, Math. Ann., 158, 82-89, (1965) · Zbl 0136.02503
[9] Brown, W. G., On the enumeration of non-planar maps, Mem. Amer. Math. Soc., 65, 526-545, (1966) · Zbl 0115.40901
[10] Gao, Z., The number of rooted triangular maps on a surface, J. Combin. Theory Ser. B, 52, 236-249, (1991) · Zbl 0751.05053
[11] Gao, Z., The number of degree restricted maps on general surfaces, Discrete Math., 123, 47-63, (1993) · Zbl 0792.05072
[12] Gao, Z. C.; Liskovets, V. A.; Wormald, N., Enumeration of unrooted odd-valent regular planar maps, Ann. Combin., 13, 233-259, (2009) · Zbl 1229.05116
[13] Gao, Z. C.; Rahman, M., Enumeration of \(k\)-poles, Ann. Combin., 1, 55-66, (1997) · Zbl 0927.05038
[14] Gao, Z.; Wormald, N. C., Enumeration of rooted cubic planar maps, Ann. Comb., 6, 313-325, (2002) · Zbl 1017.05050
[15] Giorgetti, A.; Walsh, T. R.S., Efficient enumeration of rooted maps of a given orientable genus by number of faces and vertices, Ars Math. Contemp., 7, 2, 263-280, (2014) · Zbl 1317.05090
[16] Jackson, D. M.; Visentin, T. I., An Atlas of the Smaller Maps in Orientable and Non-Orientable Surfaces, (2000), Chapman and Hall
[17] Liskovets, V. A., Enumeration of nonisomorphic planar maps, Sel. Math. Sov., 4, 303-323, (1985) · Zbl 0578.05033
[18] Long, S.; Ren, H., Counting 2-connected 4-regular maps on the projective plane, Electron. J. Combin., 21, 2, (2014) · Zbl 1300.05131
[19] Mednykh, A.; Nedela, R., Enumeration of unrooted maps of a given genus, J. Combin. Theory Ser. B, 96, 5, 709-729, (2006) · Zbl 1102.05033
[20] Mullin, R. C., Enumeration of rooted triangular maps, Amer. Math. Monthly, 71, 1007-1010, (1964) · Zbl 0127.39204
[21] Mullin, R. C., On counting rooted triangular maps, Canad. J. Math., 17, 373-382, (1965) · Zbl 0142.41203
[22] Nedela, R.; d’Azevedo, A. B.; Mednykh, A., Enumeration of maps regardless of genus: Geometric approach, Discrete Math., 310, 1184-1203, (2010) · Zbl 1236.05109
[23] Nedela, R.; Mednykh, A., Enumeration of unrooted hypermaps of a given genus, Discrete Math., 310, 518-526, (2010) · Zbl 1185.05082
[24] OEIS Foundation Inc., The on-line encyclopedia of integer sequences, 2018. http://oeis.org.
[25] Omelchenko, A. V.; Krasko, E. S., Enumeration of 4-regular one-face maps, European J. Combin., 62, 167-177, (2017) · Zbl 1358.05015
[26] Ren, H.; Liu, Y., 4-regular maps on the Klein bottle, J. Combin. Theory Ser. B, 82, 118-137, (2001) · Zbl 1023.05077
[27] Ren, H.; Liu, Y., Enumeration of near-4-regular maps on the sphere and torus, Discrete Appl. Math., 110, 273-288, (2001) · Zbl 0979.05058
[28] Ren, H.; Liu, Y., The number of loopless 4-regular maps on the projective plane, J. Combin. Theory Ser. B, 84, 84-99, (2002) · Zbl 1018.05046
[29] Robinson, R. W.; Bender, E. A.; Canfield, E. R., The enumeration of maps on the torus and the projective plane, Canad. Math. Bull., 31, 257-271, (1988) · Zbl 0617.05036
[30] Singerman, D.; Jones, G. A., Theory of maps on orientable surfaces, Proc. Lond. Math. Soc., 37, 273-307, (1978) · Zbl 0391.05024
[31] Tutte, W. T., A census of planar triangulations, Canad. J. Math., 14, 21-38, (1962) · Zbl 0103.39603
[32] Tutte, W. T., A census of slicings, Canad. J. Math., 14, 708-722, (1962) · Zbl 0111.35202
[33] Tutte, W. T., A census of planar maps, Canad. J. Math., 15, 249-271, (1963) · Zbl 0115.17305
[34] Tutte, W. T., On the enumeration of planar maps, Bull. Amer. Math. Soc., 74, 64-74, (1968) · Zbl 0157.31101
[35] T.R.S. Walsh, A. Giorgetti, Constructing large tables of numbers of maps by orientable genus, 2014. https://arxiv.org/pdf/1405.0615.pdf.
[36] 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
[37] West, D. B., Introduction to Graph Theory, (2002), Pearson Education, Inc.
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.