Counting rooted maps by genus III: Nonseparable maps

A map on an orientable surface is called separable if its underlying graph can be disconnected by splitting a vertex into two pieces, each containing a positive number of edge-ends consecutively ordered with respect to counter-clockwise rotation around the original vertex. This definition is shown to be equivalent for planar maps to Tutte's definition of a separable planar map. We develop a procedure for determining the generating functions N_g,b(x) = Σ_p=0^∞n_g,b,px^p, where n_g,b,p is the number of rooted nonseparable maps with b + p edges and p + 1 vertices on an orientable surface of genus g. Similar results are found for tree-rooted maps.     

Counting rooted unicursal planar maps

This paper investigates the number of rooted unicursal planar maps and presents some formulae for such maps with four parameters： the numbers of nonrooted vertices and inner faces and the valencies of two odd vertices.     

Counting rooted maps by Genus. I

Using a combinatorial equivalent for maps, we take the first census of maps on orientable surfaces of arbitrary genus. We generalize to higher genus Tutte's recursion formula for counting slicings, and thus obtain an algorithm for counting rooted maps by genus, number of edges, and number of vertices. We then solve a special case of this recursion formula, to count slicngs with one face by genus. This leads to an explicit formula which counts rooted maps with one face by genus and number of edges.     

Counting rooted 4-regular unicursal planar maps

A map is 4-regular unicursal if all its vertices are 4-valent except two odd-valent vertices. This paper investigates the number of rooted 4-regular unicursal planar maps and presents some formulae for such maps with four parameters: the number of edges, the number of inner faces and the valencies of the two odd vertices.     

Counting rooted near-4-regular Eulerian maps on some surfaces

In this article the rooted planar near-4-regular Eulerian trails are enumerated and an explicit formula for such maps is presented. Further, the rooted near-4-regular Eulerian maps on the torus are counted in an exact way.     

Counting alternating knots by genus

It is shown that the number of alternating knots of given genus g>1 grows as a polynomial of degree 6g−4 in the crossing number. The leading coefficient of the polynomial, which depends on the parity of the crossing number, is related to planar trivalent graphs with a Bieulerian path. The rate of growth of the number of such graphs is estimated.     

ENUMERATING ROOTED LOOPLESS PLANAR MAPS

This paper provides the following results.1.The equivalence between the method described by W.T.Tutte for determining parametricexpressions of certain enumerating functions and the one which the author used in [2] for findingthe parametric expression of the generating function of rooted general planar maps dependent on theedge number,is shown.2.The number of rooted boundary loop maps,i.e.,maps for each of which all the edges on theboundary of the outer face are loops,with the edge number given is found.3.The number of rooted nearly loopless planar maps,i.e.,loopless maps and maps having exactlyone loop which is just the rooted edge and does not form the boundary of the outer face,with givenedge number is also found.4.The recursive formula satisfied by the number of rooted loopless planar maps dependent onthe edge number is derived.5.In addition,the number of loop rooted maps,i.e.,maps in each of which there is only one loopwhich is just the rooted edge,dependent on the edge number is obtained at the sam     

Enumeration of multi-colored rooted maps

We present a study of n-colored rooted maps in orientable and locally orientable surfaces. As far as we know, no work on these maps has yet been published. We give a system of n functional equations satisfied by n-colored orientable rooted maps regardless of genus and with respect to edges and vertices. We exhibit the solution of this system as a vector where each component has a continued fraction form and we deduce a new equation generalizing the Dyck equation for rooted planar trees. Similar results are shown for n-colored rooted maps in locally orientable surfaces.     

Enumerating rooted simple planar maps

The main purpose of this paper is to find the number of combinatorially distinct rooted simpleplanar maps,i.e.,maps having no loops and no multi-edges,with the edge number given.We haveobtained the following results.1.The number of rooted boundary loopless planar [m,2]-maps.i.e.,maps in which there areno loops on the boundaries of the outer faces,and the edge number is m,the number of edges on theouter face boundaries is 2,is(?)for m≥1.G_0~N=0.2.The number of rooted loopless planar [m,2]-maps is(?)3.The number of rooted simple planar maps with m edges H_m~s satisfies the following recursiveformula:(?)where H_m~(NL) is the number of rooted loopless planar maps with m edges given in [2].4.In addition,γ(i,m),i≥1,are determined by(?)for m≥i.γ(i,j)=0,when i>j.     

Enumeration of rooted planar halin maps

A Halin map is a kind of planar maps oriented by a tree. In this paper the rooted halin maps with the vertex partition as parameters are enumerated such that a famous result on rooted trees due to Harary. Prins, and Tutte is deduced as. a special ease. Further, by using Lagrangian inversion to obtain a number of summation free formulae dixectly, the various kinds of rooted Halin maps with up to three parameters have been counted.     

Enumeration of rooted nonseparable outerplanar maps

In this paper, the number of combinatorially distinct rooted nonseparable outerplanar maps withm edges and the valency of the root-face being n is found to be(m-1)! (m-2) !:(n-1)!(n-2)! (m-n)!(m-n 1)!and, the number of rooted nonseparable outerplanar maps with m edges is also determined to be(2m-2)!:(m-1)!m!,which is just the number of distinct rooted plane trees with m-1 edges.     

Counting unrooted planar maps

Two planar maps are identified if one can be transformed to the other by any homeomorphism of the sphere. The number of such maps is found by determining the numbers of maps which have been rooted in various ways.     

The number of rooted Eulerian planar maps

In this paper we provide a solution of the functional equation unsolved in the paper, by the second author, "On functional equations arising from map enumerations" that appeared in Discrete Math, 123: 93-109 (1993). It is also the number of combinatorial distinct rooted general eulerian planar maps with the valency of root-vertex, the number of non-root vertices and non-root faces of the maps as three parameters. In particular, a result in the paper, by the same author, "On the number of eulerian planar map...     

Almost all rooted maps have large representativity

Let M be a map on a surface S. The edge-width of M is the length of a shortest noncontractible cycle of M. The face-width (or, representativity) of M is the smallest number of intersections a noncontractible curve in S has with M. (The edge-width and face-width of a planar map may be defined to be infinity.) A map is a large-edge-width embedding (LEW-embedding) if its maximum face valency is less than its edge-width. For several families of rooted maps on a given surface, we prove that there are positive constants C₁ and C₂, depending on the family and the surface, such that

• 1 almost all maps with n edges have face-width and edge-width greater than c₁ log n, and
• 2 the fraction of such maps that are LEW-embeddings and the fraction that are not LEW-embeddings both exceed n^{? >C2}.

     

The number of rooted circuit boundary maps

In this article, the authors discuss two kinds of new planar maps： pan-fan maps and circuit boundary maps, and provide explicit expressions about their enumerating functions with different parameters. Meanwhile, two explicit counting formulas for circuit cubic boundary maps with two parameters; the size and the valency of the root-face, are also extracted.     

Counting non-isomorphic three-connected planar maps

A counting formula for the number of non-isomorphic planar maps with m edges was obtained by V. A. Liskovets, and non-isomorphic 2-connected planar maps were counted by Liskovets and the author. R. W. Robinson's generalization of Polya's counting theory can be applied to these formulae to count, in polynomial time, non-isomorphic planar maps satisfying various sets of restrictions. Here two sets of planar maps are counted: maps with given 2-connected components, and 3-connected maps.     

Counting numerical semigroups by genus and even gaps

Let $n_g$ be the number of numerical semigroups of genus $g$. We present an approach to compute $n_g$ by using even gaps, and the question: Is it true that $n_{g+1}>n_g$? is investigated. Let $N_{\gamma }\left(g\right)$ be the number of numerical semigroups of genus $g$ whose number of even gaps equals $\gamma$. We show that $N_{\gamma }\left(g\right)=N_{\gamma }\left(3\gamma \right)$ for $\gamma \le ?g∕3?$ and $N_{\gamma }\left(g\right)=0$ for $\gamma >?2g∕3?$; thus the question above is true provided that $N_{\gamma }(g+1)>N_{\gamma }\left(g\right)$ for $\gamma =?g∕3?+1,\dots ,?2g∕3?$. We also show that $N_{\gamma }\left(3\gamma \right)$ coincides with $f_{\gamma }$, the number introduced by Bras-Amorós (2012) in connection with semigroup-closed sets. Finally, the stronger possibility $f_{\gamma }～{\phi }^{2\gamma }$ arises being $\phi =(1+\sqrt{5})∕2$ the golden number.