×

zbMATH — the first resource for mathematics

Relations fonctionnelles et dénombrement des cartes pointées sur le tore. (Functional relations and the enumeration of rooted genus one maps). (French) Zbl 0628.05040
The enumeration of maps on the torus was briefly discussed in [W. Brown, Mem. Am. Math. Soc. 65, 1-42 (1966; Zbl 0149.212)], and an algorithm for counting rooted toroidal maps by number of vertices and edges was presented by the reviewer in [T. R. S. Walsh and A. B. Lehman, J. Comb. Theory, Ser. B 13, 192-218 (1972; Zbl 0228.05108)]. A generating function for counting rooted toroidal maps by number of edges was presented in [E. A. Bender, E. A. Canfield and R. W. Robinson, “The enumeration of maps on the torus and the projective plane”, Can. Math. Bull. (to appear)].
Independently of [Bender et al., op. cit.], the paper under review finds not only generating functions but also explicit formulae for counting rooted toroidal maps, both by number of edges and vertices and by number of edges alone. The formula for n-edged maps is quoted to show its simplicity: \[ \sum^{n-2}_{k=0}2^{n-3-k}(3^{n-1}-3^ k)\left( \begin{matrix} n+k\\ k\end{matrix} \right). \] The author promises to count rooted maps of arbitrary orientable genus. The reviewer hopes that the methods of the present paper and those of [Bender et al., op. cit.] can be combined to solve the non-orientable case as well.
Reviewer: T.Walsh

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 hypercartes planaires pointées, () · Zbl 0617.05037
[3] Arquès, S, LES hypercartes planaires sont des arbres très bien étiquetés, Discrete math., 58, 11-24, (1986) · Zbl 0602.05023
[4] Arquès, D, Une nouvelle bijection entre hypercartes planaires et arbres très bien étiquetés. calcul formel sur LES fractions multicontinues, J. europ. combin., (Décembre 1984), à paraître
[5] Arquès, D; Françon, J, Arbres bien étiquetés et fractions multicontinues, () · Zbl 0551.05044
[6] Brown, W.G, On the enumeration of non planar maps, Mem. amer. math. soc., 65, 1-42, (1966) · Zbl 0149.21201
[7] Cori, R, Un code pour LES graphes planaires et ses applications, Astérisque, S.M.F., no. 27, (1975) · Zbl 0313.05115
[8] Cori, R; Hardouin-Duparc, J, Manipulation des Cartes planaires à partir de leur codage, (), Bordeaux · Zbl 0341.05127
[9] Cori, R; Vauquelin, B, Planar maps are well labeled trees, Canad. J. math., 33, No. 5, 1023-1042, (1981) · Zbl 0415.05020
[10] Goulden, I.P; Jackson, D.M, Combinatorial enumeration, () · Zbl 0687.05003
[11] Tutte, W.T, A census of slicings, Canad. J. math., 14, 708-722, (1962) · Zbl 0111.35202
[12] Tutte, W.T, A census of planar maps, Canad. J. math., 15, 249-271, (1963) · Zbl 0115.17305
[13] Tutte, W.T, On the enumeration of planar maps, Bull. amer. math. soc., 74, 64-74, (1968) · Zbl 0157.31101
[14] Walsh, T.R.S, Combinatorial enumeration of non planar maps, () · Zbl 0443.05050
[15] 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
[16] 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
[17] Walsh, T.R.S; Lehman, A.B, Counting rooted maps by genus. III. nonseparable maps, J. combin. theory ser. B, 18, 222-259, (1975) · Zbl 0299.05110
[18] Walsh, T.R.S, A polynomial-time algorithm for counting rooted toroïdal maps, ARS combin., 16, 49-56, (1983) · Zbl 0553.05041
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.