射影平面上的对偶无环不可分近三角剖分地图

本文研究了球面和射影平面上对偶无环不可分近三角剖分带根地图的以根面次和内面数为参数的计数问题,得到了这类地图在球面和射影平面上的计数函数满足的方程.还得到了射影平面上2连通地图一个参数的显示表达式和渐近估计式.     

Enumeration of loopless maps on the projective plane

In this paper we study the rooted loopless maps on the sphere and the projective plane with the valency of root-face and the number of edges as parameters. Explicit expression of enumerating function is obtained for such maps on the sphere and the projective plane. A parametric expression of the generating function is obtained for such maps on the projective plane, from which asymptotic evaluations are derived.     

球面和射影平面上不可分地图的色和

给出了球面和射影平面上带根不可分地图的色和方程,从色和方程导出了球面和射影平面上带根一般不可分地图、二部地图的计数函数方程. 利用色和理论,研究不同类地图的计数问题,得到了一种研究计数问题的新方法. 此外,还得到了一些计数显示表达式.     

Chromatic sums of biloopless nonseparable near-triangulations on the projective plane

In this paper, the chromatic sum functions of rooted biloopless nonseparable near-triangulations on the sphere and the projective plane are studied. The chromatic sum function equations of such maps are obtained. From the chromatic sum equations of such maps, the enumerating function equations of such maps are derived. An asymptotic evaluation and some explicit expression of enumerating functions are also derived.     

Chromatic sums of nonseparable near-triangulations on the projective plane

In this paper, we study the chromatic sum functions of rooted nonseparable near-triangulations on the sphere and the projective plane. The chromatic sum function equations of such maps are obtained. From the chromatic sum equations of such maps, the enumerating function equations of such maps are derived. Applying chromatic sum theory, the enumerating problem of different sorts maps can be studied, and a new method of enumeration can be obtained. Moreover, an asymptotic evaluation and some explicit expression of enumerating functions are also derived.     

Chromatic sums of rooted triangulations on the projective plane

In this paper we study the chromatic sum functions for rooted nonseparable near-triangular maps on the projective plane. A chromatic sum equation for such maps is obtained.     

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…     

COUNTING ROOTED EULERIAN MAPS ON THE PROJECTIVE PLANE

1IntroductionAsurfaceisacompactclosed2-manifold.Theorielltable(non-orielltable)surfaceofgenuskisthespherewitllkhandles(crosscaPs)denotedbySk(Nk).AmapMollSk(Nk)meansthatitsunderlyinggraphnlaybedrownou(embeddedin)itsuchthatllthpairofedgesintersectataninnerpoilltalldeachfaceishomeomorphictothedisc.Amapisrootedifanedgewithadirectiollalongtheedge,alldasideoftl1eedgeisdistinguisl1ed.Tworootedmapsareconsideredtobethesal11eifthereisanisomorphismpreserviIlgtl1erooting.ArootedEuleriall1llapissuchaon…     

Chromatic sums of nonseparable simple maps on the plane

In this paper we study the chromatic sum functions for rooted nonseparable simple maps on the plane. The chromatic sum function equation for such maps is obtained. The enumerating function equation of such maps is derived by the chromatic sum equation of such maps. From the chromatic sum equation of such maps, the enumerating function equation of rooted nonseparable simple bipartite maps on the plane is also derived.     

Chromatic sums of general maps on the sphere and the projective plane

In this paper, we study the chromatic sum functions of rooted general maps on the sphere and the projective plane. The chromatic sum function equations of such maps are obtained. From the chromatic sum equations of such maps, the enumerating function equations of rooted loopless maps, bipartite maps and Eulerian maps are also derived. Moreover, some explicit expressions of enumerating functions are also derived.     

Enumeration on Nonseparable Planar Maps

This paper provides some functional equations satisfied by the generating functions for nonseparable rooted planar maps with the valency of root-vertex, the number of edges and the valency of root-faces of the maps as three parameters. But the solutions of these equations can only be obtained indirectly by considering some relations between nonseparable and general rooted planar maps. One of them is an answer to the open problem 6.1 in Liu (1983, Comb. Optim. CORR83-26, University of Waterloo).     

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.     

Vertex-transitive graphs and vertex-transitive maps

We consider vertex-transitive graphs embeddable on a fixed surface. We prove that all but a finite number of them admit embeddings as vertex-transitive maps on surfaces of nonnegative Euler characteristic (sphere, projective plane, torus, or Klein bottle). It follows that with the exception of the cycles and a finite number of additional graphs, they are factor graphs of semiregular plane tilings. The results generalize previous work on the genus of minimal Cayley graphs by V. Proulx and T. W. Tucker and were obtained independently by C. Thomassen, with significant differences in the methods used. Our method is based on an excursion into the infinite. The local structure of our finite graphs is studied via a pointwise limit construction, and the infinite vertex-transitive graphs obtained as such limits are classified by their connectivity and the number of ends. In two appendices, we derive a combinatorial version of Hurwitz's Theorem, and classify the vertex-transitive maps on the Klein bottle.     

Counting unrooted maps on the plane

A planar map is a 2-cell embedding of a connected planar graph, loops and parallel edges allowed, on the sphere. A plane map is a planar map with a distinguished outside (“infinite”) face. An unrooted map is an equivalence class of maps under orientation-preserving homeomorphism, and a rooted map is a map with a distinguished oriented edge. Previously we obtained formulae for the number of unrooted planar n-edge maps of various classes, including all maps, non-separable maps, eulerian maps and loopless maps. In this article, using the same technique we obtain closed formulae for counting unrooted plane maps of all these classes and their duals. The corresponding formulae for rooted maps are known to be all sum-free; the formulae that we obtain for unrooted maps contain only a sum over the divisors of n. We count also unrooted two-vertex plane maps.     

Chromatic sums of singular maps on some surfaces

A map is singular if each edge is on the same face on a sruface (i.e., those have only one face on a surface). Because any map with loop is not colorable, all maps here are assumed to be loopless. In this paper povides the explicit expression of chromatic sum functions for rooted singular maps on the projective plane, the torus and the Klein bottle. From the explicit expression of chromatic sum functions of such maps, the explicit expression of enum erating functions of such maps are also derived.     

Nonrevisiting paths on surfaces

The nonrevisiting path conjecture for polytopes, which is equivalent to the Hirsch conjecture, is open. However, for surfaces, the nonrevisiting path conjecture is known to be true for polyhedral maps on the sphere, projective plane, torus, and a Klein bottle. Barnette has provided counterexamples on the orientable surface of genus 8 and nonorientable surface of genus 16. In this note the question is settled for all the remaining surface except the connected sum of three copies of the projective plane.     

Stack words, standard Young tableaux, permutations with forbidden subsequences and planar maps

Stack words stem from studies on stack-sortable permutations and represent classical combinatorial objects such as standard Young tableaux, permutations with forbidden sequences and planar maps. We extend existing enumerative results on stack words and we also obtain new results. In particular, we make a correspondence between nonseparable 3×n rectangular standard Young tableaux (or stack words where elements satisfy a ‘Towers of Hanoi’ condition) and nonseparable cubic rooted planar maps with 2n vertices enumerated by 2ⁿ(3n)!/((2n+1)!(n+1)!). Moreover, these tableaux without two consecutive integers in the same row are in bijection with nonseparable rooted planar maps with n+1 edges enumerated by 2(3n)!/((2n+1)!(n+1)!).     

3-edge-connected embeddings have few singular edges

We show that a 3-edge-connected graph embedded in a surface of Euler characteristic χ has at most 3 – 3χ singular edges, except in the projective plane, where it has at most one singular edge, and the sphere, where it has none. This bound is best possible for all surfaces.     

Chromatic sums of 2-edge-connected maps on the projective plane

This paper provides the chromatic sum function equations of rooted 2-edge-connected maps on the projective plane. The enumerating function equations of rooted 2-edge-connected loopless maps and rooted 2-edge-connected bipartite maps on the projective plane are derived by the chromatic sum function equation of rooted 2-edge-connected maps on the projective plane.     

循环图C(2n,2)(n＞2)在射影平面上的嵌入计数

图在球面上的嵌入个数即柔性问题已经由刘彦佩教授解决,研究图在射影平面上的嵌入亦有着重要的意义。本文利用刘彦佩教授创建的嵌入联树模型得出了循环图C(2n,2)(n>2)在射影平面上的嵌入个数。