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.     

An analogue of the Harer-Zagier formula for unicellular maps on general surfaces

A unicellular map is the embedding of a connected graph in a surface in such a way that the complement of the graph is simply connected. In a famous article, Harer and Zagier established a formula for the generating function of unicellular maps counted according to the number of vertices and edges. The keystone of their approach is a counting formula for unicellular maps on orientable surfaces with n edges, and with vertices colored using every color in [q] (adjacent vertices are authorized to have the same color). We give an analogue of this formula for general (locally orientable) surfaces.Our approach is bijective and is inspired by Lass?s proof of the Harer-Zagier formula. We first revisit Lass?s proof and twist it into a bijection between unicellular maps on orientable surfaces with vertices colored using every color in [q], and maps with vertex set [q] on orientable surfaces with a marked spanning tree. The bijection immediately implies Harer-Zagier?s formula and a formula by Jackson concerning bipartite unicellular maps. It also shed a new light on constructions by Goulden and Nica, Schaeffer and Vassilieva, and Morales and Vassilieva. We then extend the bijection to general surfaces and obtain a correspondence between unicellular maps on general surfaces with vertices colored using every color in [q], and maps on orientable surfaces with vertex set [q]with a marked planar submap. This correspondence gives an analogue of the Harer-Zagier formula for general surfaces. We also show that this formula implies a recursion formula due to Ledoux for the numbers of unicellular maps with given numbers of vertices and edges.     

环面上一般有根地图的计数

这篇文章给出了环面上以内面个数，根面次和非根节点个数为参数的一般有根地图的计数方程，导出了以内面个数和非根节点个数为参数的这类地图的计数方程的精确解。作为推论，推出了以边数为参数的这类地图的个数，其近似解在文献[2]中已讨论。     

Enumeration of maps on the projective plane

1. IntroductionA lnap is rooted if an edge is distinguished togetl1er with an end and a side of the edge.An edge belo11ging to only one face is called double (or 8ingular by some author), al1 othersbelonging to exactly two faces are called s1ngle. The enumeration of rooted p1anar maps wasfirst introduced by Tutte['], Techniques originated by Tutte [2,3l for enumerating variousclasses of rooted Inaps on tIle sphere are here applied to the c1asses of alI rooted maps onthe projective plane. Th…     

Simplification of formulas for the number of maps on surfaces

Two combinatorial identities obtained by the author are used to simplify formulas for the number of general rooted cubic planar maps, for the number of g-essential maps on surfaces of small genus, and also for rooted Eulerian maps on the projective plane. Besides, an asymptotics for the number of maps with a large number of vertices is obtained.     

数有根近2-正则平面地图

The number of rooted nearly 2-regular maps with the valency of root-vertex, the number of non-rooted vertices and the valency of root-face as three parameters is obtained. Furthermore, the explicit expressions of the special cases including loopless nearly 2-regular maps and simple nearly 2-regular maps in terms of the above three parameters are derived.     

An inductive definition of cubic toroidal maps

An inductive definition of the class of all cubic toroidal maps will be given. Moreover, it will be demonstrated how this definition can be used to develop an efficient algorithm which constructs all cubic toroidal maps with a limited number of vertices.     

Separating Maps of the Lattice E 8 and Triangulations of the Eight-Dimensional Torus

Our goal is to build triangulations of the eight-dimensional torus with 511 vertices, 511 being the smallest number of vertices of the known triangulations of the torus. We define the separating maps from the lattice E ₈ to Z / 511 Z and we establish the list of such maps up to symmetry. Received February 26, 1999, and in revised form June 9, 1999.     

On Triangulations with High Vertex Degree

We solve three enumerative problems concerning the families of planar maps. More precisely, we establish algebraic equations for the generating function of loopless triangulations in which all vertices have degree at least d, for a certain value d chosen in {3, 4, 5}. The originality of the problem lies in the fact that degree restrictions are placed both on vertices and faces. Our proofs first follow Tutte’s classical approach: We decompose maps by deleting the root-edge and translate the decomposition into an equation satisfied by the generating function of the maps under consideration. Then we proceed to solve the equation obtained using a recent technique that extends the so-called quadratic method. Received January 25, 2006     

Neighborly maps with few vertices

A neighborly map is a simplicial 2-complex which decomposes a closed 2-manifold without boundary, such that any two vertices are joined by an edge (1-cell) in the complex. We find and describe all the neighborly maps with Euler characteristicX>−10 (i.e., genusg<6, if orientable) or, equivalently, all the neighborly maps withV<12 vertices.     

Regular maps whose groups do not act faithfully on vertices,edges, or faces

Regular maps whose automorphism groups do not have faithful action on vertices, edges, or faces are analysed in detail.     

Chromatic sum equations for rooted cubic planar maps

This paper provides a functional equation satisfied by rooted nearly cubic planar maps. By a nearly cubic map is meant such a map that all the vertices have valency 3 with the exception of at most the root-vertex. And, as a consequence, the corresponding functional equation for rooted cubic planar maps is found.     

The invertibility of the isoparametric mapping for pyramidal and prismatic finite elements

Summary. We consider the isoparametric transformation, which maps a given reference element onto a global element given by its vertices, for multi-linear finite elements on pyramids and prisms. We present easily computable conditions on the position of the vertices, which ensure that the isoparametric transformation is bijective. Received May 7, 1999 / Revised version received April 28, 2000 / Published online December 19, 2000     

Isomorphism-free lexicographic enumeration of triangulated surfaces and 3-manifolds

We present a fast enumeration algorithm for combinatorial 2- and 3-manifolds. In particular, we enumerate all triangulated surfaces with 11 and 12 vertices and all triangulated 3-manifolds with 11 vertices. We further determine all equivelar polyhedral maps on the non-orientable surface of genus 4 as well as all equivelar triangulations of the orientable surface of genus 3 and the non-orientable surfaces of genus 5 and 6.     

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.     

New bijective links on planar maps via orientations

This article presents new bijections on planar maps. At first a bijection is established between bipolar orientations on planar maps and specific “transversal structures” on triangulations of the 4-gon with no separating 3-cycle, which are called irreducible triangulations. This bijection specializes to a bijection between rooted non-separable maps and rooted irreducible triangulations. This yields in turn a bijection between rooted loopless maps and rooted triangulations, based on the observation that loopless maps and triangulations are decomposed in a similar way into components that are respectively non-separable maps and irreducible triangulations. This gives another bijective proof (after Wormald’s construction published in 1980) of the fact that rooted loopless maps with n edges are equinumerous to rooted triangulations with n inner vertices.     

A bijection between ordered trees and bicoloured ordered trees

A bijection is introduced between ordered trees and bicoloured ordered trees, which maps leaves in an ordered tree to odd height vertices in the related tree. Consequently, a bijection between two sets of bridges specified with four parameters is derived.     

On weakly neighborly polyhedral maps of arbitrary genus

A weakly neighborly polyhedral map (w.n.p. map) is a 2-dimensional cell-complex which decomposes a closed 2-manifold without boundary, such that for every two vertices there is a 2-cell containing them. We lay the foundation for an investigation of the w.n.p. maps of arbitrary genus. In particular we find all the w.n.p. maps of genus 0, we prove that for everyg> the number of w.n.p. maps of genusg (orientable or not) is finite, and we find an upper bound for the number of vertices in a w.n.p. map of genusg>0. This upper bound grows as (4g(^2/3) wheng→∞.     

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.     

Graphs with three mutually pseudo-similar vertices

Vertices u and v of a graph X are pseudo-similar if X ? u ? X ? v but no automorphism of X maps u to v. We describe a group-theoretic method for constructing graphs with a set of three mutually pseudo-similar vertices. The method is used to construct several examples of such graphs. An algorithm for extending, in a natural way, certain graphs with three mutually pseudo-similar vertices to a graph in which the three vertices are similar is given. The algorithm suggests that no simple characterization of graphs with a set of three mutually pseudo-similar vertices can exist.