Enumeration of Unrooted Odd-Valent
Regular Planar Maps

Zhicheng Gao^{1}, Valery
A. Liskovets^{2}, and Nicholas
Wormald^{3}

zgao@math.carleton.ca

liskov@im.bas-net.by

nwormald@uwaterloo.ca

Annals of Combinatorics 13 (2) pp.233-259 June, 2009

Abstract:

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 f
References:

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.