# zbMATH — the first resource for mathematics

Efficient enumeration of rooted maps of a given orientable genus by number of faces and vertices. (English) Zbl 1317.05090
Here, 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.

##### MSC:
 05C30 Enumeration in graph theory
Full Text: