×

The enumeration of rooted nonseparable nearly cubic maps. (English) Zbl 0934.05074

From the authors’ introduction: “A rooted near-cubic planar map is a rooted connected one in which all of its non-root vertices are 3-valent. If the root-vertex is also 3-valent, then the map is called a rooted cubic planar map. A map \(M\) is called separable if its edge set can be partitioned into two disjoint non-null submaps \(S\) and \(T\) so that there is just one vertex incident with both \(S\) and \(T\). The vertex is said to be a separable vertex of \(M\). A rooted nonseparable near-cubic planar map is a rooted one without any separable vertex. \(\dots\). In the following we will enumerate rooted nonseparable cubic and nearly cubic planar maps. Several explicit expressions of the enumerating functions for these maps will be derived and two of them will be summation-free.” The discussion is very intricate, involving many similarly-named maps and functions. (For example, on page 12, one has to consider \({\mathcal M}_{ns}\), \({\mathcal M}_{ns}^{(0)}\), \({\mathcal M}_{ns}^{(1)}\), \({\mathcal M}_{ns}^{(2)}\), \({\mathcal M}_{(ns)}^{(1)}\), \({\mathcal M}_{(ns)}^{(2)}\), and \({\mathcal M}_{ns2}\) (which may be a misprint).) From the last section: Of course, the parametric expressions given \(\dots\). allow us to employ Lagrangian inversion with three variables for finding an explicit expression of the enumerating function \(\dots\). But we cannot do so in this paper because the complications are involved, obviously. We leave the detailed discussion to a forthcoming paper in order to avoid too much space to be occupied here.

MSC:

05C30 Enumeration in graph theory
05A15 Exact enumeration problems, generating functions
PDFBibTeX XMLCite
Full Text: DOI