树的自同构群的一个新的恒等式

通过计数给定基础图的标根地图数，本文得到了树的自同构群的如下恒等式∑T∈T(n)Πd∈D(T)^(d-1)！/|AutT|=（2n-1)!/n!(n 1)!，这里T（n),D(T)分别表示n阶不同构树集，树T的次序列。     

关于4-连通三角剖分的计数

本文讨论4-连通极大平面地图的计数问题.从地图对偶的角度考虑,它等价 于强3-连通3-正则有根平面地图的计数问题.在此,我们获得了具有一个和两个变 量的精确计数公式.本文的结果简化并推广了文[1,2]中的相应结果.     

ON THE VERTEX PARTITION EQUATION OF LOOPLESS EULERIAN PLANAR MAPS

The functional equation satisfied by the vertex partition function of rooted loopless Eulerianplanar maps is provided. As applications, the enumerating equations for general and regular casesof this kind of maps are also discussed.     

CHROMATIC ENUMERATION FORROOTED OUTERPLANAR MAPS

Let G(m,s,t,λ)be the number of ways of λ-coloring all the rooted nonseparableouterplanar maps which are simple and have the edge number m,the valency s of theroot-face,and the valency t of the root-vertex.The chromatic enumerating functiong(x,y,z;λ.)=G(m,s,t;λ)x~my~sz~tis determined.Meanwhile,a number of explicit formulae for enumerating this kindofmaps in general case and in Lipartite case are provided.     

STRONG EMBEDDINGS OF PLANAR GRAPHS ON HIGHER SURFACES

In this paper, the authors discuss the upper bound for the genus of strong embeddings for 3-connected planar graphs on higher surfaces. It is shown that the problem of determining the upper bound for the strong embedding of 3-connected planar near-triangulations on higher non-orientable surfaces is NP-hard. As a corollary, a theorem of Richter, Seymour and Siran about the strong embedding of 3-connected planar graphs is generalized to orientable surface.     

关于平面地图的计数方程

本文介绍了在平面地图的计数中所出现的函数方程的若干类型和它们的解法.并提出了一些目前有待解决的问题.     

地图着色定理与图的曲面嵌入(Ⅱ)

<正> 六、电流图 定义6.1.一个图Z,如果对于一个n阶Abel加法群Z_n,不妨就取它为modn的整数群,满足下面四个条件IC1,IC2,IC3,IC4就称之为Z_?的第一类电流图.并记之为Z_n(I). IC1,Z的所有顶点的次非3即1. IC2,有α_1=[n/2]条边与群元素1,2,…,[n/2],作为电流,一一对应,使得悬挂边(即有次为1的端点)上的电流k与n互素,即(k,n)=1.还可赋次为1的顶点以符     

关于3－正则子图问题的一个注记

这篇注记证明判断一个图是否有３－正则子图的问题，即使对于节点次不超过４的平面图，仍然是ＮＰ－完全的。而且，此结果是最好的可能。     

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

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

我所了解的图论(五)

第八讲通往拟阵回顾卅年代在剑桥的四人小组的活动,我注意到了用代数的形式来整理那些研究工作的趋势.首先提出这种代数化处理方式的是Smith.他因厌烦于画那些3-正则图,因此试图丢掉边、点等,而代之以由三个点组成的集.用点表示图中的边,三个点组成的集表示图的顶点.看起来这似乎是一件小事,然而这却是陷入一个无底深渊的第一步.不久,他又将图中的边看作为一个mod2向量空间的点.同时,将和为零的点的三元组看作为图的顶点.然而,这种做法又很快地消声匿迹,因为保持三元性是不必要的,只需线性关系.