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向量空间的点.同时,将和为零的点的三元组看作为图的顶点.然而,这种做法又很快地消声匿迹,因为保持三元性是不必要的,只需线性关系.     

k-VALENT MAPS ON THE SURFACES

In this paper,the works of Kotzig,Zaks and the author have been generalized and unified.A number of new results have also been obtained.     

平面图的理论与四色问题(Ⅰ)——平面性与对偶性

四色问题是与数论中的Fermat猜想,函数论中的Riemann假设相提并论的数学难题。1976年,K.I.Appel和W.Haken在美国数学会的通报上声明借助电子计算机解决了这个问题。他们的基本方法是在所有平面图的可约构形中找出一个不可免的完备集。占用计算时间1200多个小时。这样的工作量是人工难以胜任的。另一方面,E.F.Mcore却发现了一个平面图,其任何一个可约构形的外圈长均至少为12。由此观之,这种方法不大可能作出本质上的简化以致达到人工通常所能胜任的地步。然而,如何只通过数学上的逻辑推理证明四色定理,仍是一个重要的理论课题。     

THEORETICAL RESULTS ON AT MOST 1-BEND EMBEDDABILITY OF GRAPHS

1. Introduction Let κ be a non-negative integer. A κ-bend graph is a plane graph in which every edgeis a broken line consisting of at most κ+ 1 horizontal or vertical segments. A bend is any point which is the intersection of a horizontal segment and a verticalsegment of an edge. A planar graph G is κ-rectilinear if it admits a plane embedding Gwhich is a κ-bend graph. In this case G is said to be a κ-embedding of G.     

有根平面地图的节点剖分计数

本文试图以带一个线性泛函的方程的观点统一处理迄今为止所得到的所有类型的有根平面地图依节点剖分的计数。例如:有根平面树、冬梅地图、单圈地图、一般平面地图、不可分离平面地图、一般Euler平面地图、不可分离Euler平面地图、一般外平面地图以及不可分离外平面地图等。并且,提出了一些目前有待解决的问题。