Efficient enumeration of rooted maps of a given orientable genus by number of faces and vertices.

*(English)*Zbl 1317.05090Here, a map is a 2-cell embedding of a graph (with possible loops and multiple edges) in a 2-dimensional surface. A face of a map is a connected component of the complement of the graph. The surface is here assumed to be orientable, i.e. with a given orientation attached to it (clockwise or counter-clockwise). A genus \(g\)-map is a map on a surface of genus \(g\in \{0,1,2,\ldots\}\). A rooted map is a map with a distinguished root, in the form of a semi-edge (or an “edge-end” that the authors call a dart; each edge has exactly two darts). It is also assumed that each map is equipped with a cyclic order on the darts incident to each vertex, representing the order these darts are encountered during a rotation around the vertex according to the given orientation. Two such rooted maps are then equivalent if there is a graph isomorphism from one map to the other that respects the orientation, the root, and the cyclic order. This paper studies the generating function
\[
M_g(w,u) = \sum_{v,f\geq 1}m_g(v,f)w^vu^f,
\]
where \(m_g(v,f)\) is the number of isomorphism classes of rooted \(g\) maps with \(v\) vertices and \(f\) faces. By writing the variables \(w\) and \(u\) in terms of new parameters \(p\) and \(q\) as \(w = p(1 - p - 2q)\) and \(u = q(1 - 2p - q)\), it is already known that
\[
M_g(w,u) = \frac{pq(1 - p - q)P_g(p,q)}{((1 - 2p - 2p)^2 - 4pq)^{5g-3}},
\]
where \(P_g(p,q)\) is a symmetric polynomial in \(p\) and \(q\) of total degree \(6q-6\) with integral coefficients. These polynomials \(P_g\) have previously been computed for \(g = 2,3\). In this paper, they are computed for \(g = 4,5,6\). In doing so, the authors simplify previously known recurrence relations they satisfy, and have written a C++ program to compute them.

Reviewer: Geir Agnarsson (Fairfax)

##### MSC:

05C30 | Enumeration in graph theory |