×

zbMATH — the first resource for mathematics

Counting rooted maps on an orientable surface of any genus by a function of the numbers of vertices and faces. (Énumération des cartes pointées sur une surface orientable de genre quelconque en fonction des nombres de sommets et de faces.) (French) Zbl 1029.05073
Summary: We give here general formulas for the generating functions counting rooted maps on an orientable surface by the numbers of vertices and faces. All these generating functions appear to be rational functions of the same parametric system of the variables counting the numbers of vertices and faces. We make explicit these functions for rooted maps of genus 0, 1, 2, and 3. The solutions for genus 2 and 3 are new results about maps. Moreover, our general formulas refine these of E. A. Bender et al., answering a question left open in their articles on this subject.

MSC:
05C30 Enumeration in graph theory
05A15 Exact enumeration problems, generating functions
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, 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, 244-257, (1987) · Zbl 0628.05040
[3] Arquès, D.; Jacques, I., Classification des Cartes pointées de genre 1 et relation fonctionnelle associée, Theoret. comput. sci., 117, 45-65, (1993) · Zbl 0792.05069
[4] Bender, E.A.; Canfield, E.R., The asymptotic number of rooted maps on a surface, J. combin. theory ser. A, 43, 244-257, (1986) · Zbl 0606.05031
[5] Bender, E.A.; Canfield, E.R., The number of rooted maps on an orientable surface, J. combin. theory ser. B, 53, 293-299, (1991) · Zbl 0751.05052
[6] Bender, E.A.; Canfield, E.R.; Richmond, L.B., The asymptotic number of rooted maps on a surface. II. enumeration by vertices and faces, J. combin. theory ser. A, 63, 318-329, (1993) · Zbl 0777.05065
[7] Bender, E.A.; Canfield, E.R.; Robinson, R.W., The enumeration of maps on the torus and the projective plane, Canad. math. bull., 31, 257-271, (1988) · Zbl 0617.05036
[8] Codi, R., Un code pour LES graphes planaires et ses applications, Asterisque, 27, (1975)
[9] Tutte, W.T., A census of planar maps, Canad. J. math., 15, 249-271, (1963) · Zbl 0115.17305
[10] Tutte, W.T., On the enumeration of planar maps, Bull. amer. math. soc., 74, 64-74, (1968) · Zbl 0157.31101
[11] 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
[12] Walsh, T.R.S.; Lehman, A.B., Counting rooted maps by genus, II, J. combin. theory ser. B, 13, 122-141, (1972) · Zbl 0228.05108
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.