<%@ Page Language="C#" MasterPageFile="~/Main.master" AutoEventWireup="true" Title="Volume 13 Issue 2" %>
Enumeration of Unrooted Odd-Valent Regular Planar Maps
Zhicheng Gao1, Valery A. Liskovets2, and Nicholas Wormald3
1School of Mathematics and Statistics, Carleton University, Ottawa, Ontario, K1S 5B6, Canada
2Institute of Mathematics, National Academy of Sciences, Minsk 220072, Belarus
3Department of Combinatorics and Optimization, University of Waterloo, Waterloo, Ontario,\break\phantom{\raisebox{1.1mm}{\footnotesize 1}}N2L 3G1, Canada
Annals of Combinatorics 13 (2) pp.233-259 June, 2009
AMS Subject Classification: 05C05, 92D15
We derive closed formulae for the numbers of rooted maps with a fixed number of vertices of the same odd degree except for the root vertex and one other exceptional vertex of degree 1. The same applies to the generating functions for these numbers. Similar results, but without the vertex of degree 1, were obtained by the first author and Rahman. We also show, by manipulating a recursion of Bouttier, Di Francesco and Guitter, that there are closed formulae when the exceptional vertex has arbitrary degree. We combine these formulae with results of the second author to count unrooted regular maps of odd degree. In this way we obtain, for each even n, a closed formula for the function fn whose value at odd positive integers $r$ is the number of unrooted maps (up to orientation-preserving homeomorphisms) with n vertices and degree $r$. The formula for fn becomes more cumbersome as $n$ increases, but for n> 2 each has a bounded number of terms independent of r.
Keywords: odd degree, unrooted map, rooted planar map, regular map, rotation, quotient map, closed formula


1. E.A. Bender and E.R. Caneld, The number of degree restricted rooted maps on the sphere, SIAM J. Discrete Math. 7 (1) (1994) 9–-15.

2. M. Bousquet, G. Labelle, and P. Leroux, Enumeration of planar two-face maps, Discrete Math. 222 (1-3) (2000) 1-–25.

3. M. Bousquet-M´elou and A. Jehanne, Polynomial equations with one catalytic variable, algebraic series and map enumeration, J. Combin. Theory Ser. B 96 (5) (2006) 623-–672.

4. J. Bouttier, P. Di Francesco, and E. Guitter, Census of planar maps: from the one-matrix model solution to a combinatorial proof, Nuclear Phys. B 645 (3) (2002) 477-–499.

5. Z.C. Gao, The number of degree restricted maps on general surfaces, Discrete Math. 123 (1-3) (1993) 47–-63.

6. Z.C. Gao and M. Rahman, Enumeration of k-poles, Ann. Combin. 1 (1) (1997) 55–-66.

7. V.A. Liskovets, A census of nonisomorphic planar maps, In: Algebraic Methods in Graph Theory, Colloq. Math. Soc. J. Bolyai, Vol. 25, North-Holland, Amsterdam, (1981) pp. 479-–494.

8. V.A. Liskovets, Enumeration of nonisomorphic planar maps, Selecta Math. Soviet. 4 (4) (1985) 304–-323.

9. V. Liskovets, Reductive enumeration under mutually orthogonal group actions, Acta Appl. Math. 52 (1-3) (1998) 91–-120.

10. V.A. Liskovets, Enumerative formulae for unrooted planar maps: a pattern, Electron. J. Combin. 11 (1) (2004) #R88.

11. V.A. Liskovets and T.R.S. Walsh, Ten steps to counting planar graphs, Congr. Numer. 60 (1987) 269–-277.

12. R.C. Mullin, On the average number of trees in certain maps, Canad. J. Math. 18 (1) (1966) 33–-41.

13. W.T. Tutte, A census of slicings, Canad. J. Math. 14 (4) (1962) 708-–722.

14. N.C. Wormald, On the number of planar maps, Canad. J. Math. 33 (1) (1981) 1–-11.