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

Arquès, Didier; Giorgetti, Alain

J. Comb. Theory, Ser. B 77, No. 1, 1-24 (1999).

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

Keywords:

generating functions

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