×

Enumeration of rooted maps on the Klein bottle. (Énumération des cartes pointées sur la bouteille de Klein.) (French) Zbl 0891.05040

Summary: We present the first enumeration of rooted maps on the Klein bottle. The series for the rooted maps drawn on the Klein bottle is the unique solution of the Tutte functional equation, which is obtained by removing the rooted edge of the map. We solve this equation using techniques usually used for maps on orientable surfaces (by Arquès in 1987, Bender and Canfield in 1991), and applied to the projective plane by Bender et al. (1988, 1993). Here, we solve in details the Tutte equation to obtain a parametric system giving the generating series for the rooted maps on the Klein bottle, with respect to the number of edges. Moreover, we give this parametric system when the enumeration is done with respect to the number of vertices and faces.

MSC:

05C30 Enumeration in graph theory
05C10 Planar graphs; geometric and topological aspects of graph theory
PDFBibTeX XMLCite
Full Text: DOI EuDML

Online Encyclopedia of Integer Sequences:

Number of rooted maps with n edges on Klein bottle.

References:

[1] 1. D. ARQUÈS et A. GIORGETTI, Énumération des cartes pointées sur une surface orientable de genre quelconque en fonction des nombres de sommets et de faces, Rapport de recherche Institut Gaspard Monge, 1997, 97-21, soumis à publication. MR1710529
[2] 2. D. ARQUÈS, Une relation fonctionnelle nouvelle sur les cartes planaires pointées, J. Combin. Theory, Ser. B, 1985, 39, p. 27-42. Zbl0571.05001 MR805455 · Zbl 0571.05001 · doi:10.1016/0095-8956(85)90036-X
[3] 3. D. ARQUÈS, Relations fonctionnelles et dénombrement des cartes pointées sur le tore, J. Combin. Theory, Ser. B, 1987, 43, p. 253-274. Zbl0628.05040 MR916371 · Zbl 0628.05040 · doi:10.1016/0095-8956(87)90002-5
[4] 4. E. BENDER et E. CANFIELD, The number of rooted maps on an orientable surface, J. Combin. Theory, Ser. B, 1991, 53, p. 293-299. Zbl0751.05052 MR1129556 · Zbl 0751.05052 · doi:10.1016/0095-8956(91)90079-Y
[5] 5. E. BENDER et E. CANFIELD, The asymptotic number of rooted maps on a surface, J. Combin. Theory, Ser. A, 1986, 43, p. 244-257. Zbl0606.05031 MR867650 · Zbl 0606.05031 · doi:10.1016/0097-3165(86)90065-8
[6] 6. E. BENDER, E. CANFIELD et R. ROBINSON, The enumeration of maps on the torus and the projective plane, Canad. Math. Bull., 1988, 31(3), p. 257-271. Zbl0617.05036 MR956356 · Zbl 0617.05036 · doi:10.4153/CMB-1988-039-4
[7] 7. E. BENDER, E. CANFIELD et R. ROBINSON, The asymptotic number of tree-rooted maps on a surface, J. Combin. Theory, Ser. A, 1988, 48, p. 156-164. Zbl0644.05027 MR949608 · Zbl 0644.05027 · doi:10.1016/0097-3165(88)90002-7
[8] 8. E. BENDER, E. CANFIELD et L. RICHMOND, The asymptotic number of rooted maps on a surface. II. Enumeration by vertices and faces, J. Combin. Theory, Ser. A, 1993, 63, p. 318-329. Zbl0777.05065 MR1223687 · Zbl 0777.05065 · doi:10.1016/0097-3165(93)90063-E
[9] 9. E. BENDER, Z. GAO, L. RICHMOND et N. WORMALD, Asymptotic properties of rooted 3-connected maps on surfaces, J. Austral. Math. Soc., 1996, 60, p. 31-41. Zbl0913.05041 MR1364552 · Zbl 0913.05041
[10] 10. W. G. BROWN, On the enumeration of non-planar maps, Mem. Amer. Math. Soc., 1966, 65. Zbl0149.21201 MR220628 · Zbl 0149.21201
[11] 11. R. CORI, Un code pour les graphes planaires et ses applications, Astérisque, S.M.F., 1975, 27. Zbl0313.05115 MR404045 · Zbl 0313.05115
[12] 12. I. P. GOULDEN et D. M. JACKSON, Maps in locally orientable surfaces, the double coset algebra, and zonal polynomials, Canad. J. Math., 1966, 48 (3), p. 569-584. Zbl0861.05062 MR1402328 · Zbl 0861.05062 · doi:10.4153/CJM-1996-029-x
[13] 13. W. S. MASSEY, Algebraic topology: an introduction, Springer-Verlag, Graduate Texts in Mathematics, 1977, 56. Zbl0361.55002 MR448331 · Zbl 0361.55002
[14] 14. W. T. TUTTE, On the enumeration of planar maps, Bull. Amer. Math. Soc., 1968, 74, p. 64-74. Zbl0157.31101 MR218276 · Zbl 0157.31101 · doi:10.1090/S0002-9904-1968-11877-4
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.