CHROMATIC SUM EQUATIONS FOR ROOTED CUBIC PLANAR MAPS

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

GENERAL THEORETICAL RESULTS ON RECTILINEAR EMBEDABILITY OF GRAPHS

In the design of certain kinds of electronic circuits the following question arises:given a non-negative integer k, what graphs admit of a plane embedding such that every edge is a broken lineformed by horizontal and vertical segments and having at mort k bends? Any such graph is said tobe k--rectilinear. No matter what k is, an obvious necessary condition for k-rectilinearity is that thedegree of each vertex does not exceed four.Our main result is that every planar graph H satisfying this condition is 3--rectilinear:in fact,it is 2--rectilinear with the only exception of the octahedron. We also outline a polynomial-timealgorithm which actually constructs a plane embedding of H with at most 2 bends (3 bends if H isthe octahedron) on each edge. The resulting embedding has the property that the total number ofbends does not exceed 2n, where n is the number of vertices of H.     

关于直径为４的图的最大亏格

该文证明了如下结果：设犌为直径为４的简单图,若犌不含３阶完全子图犓３,则犌的Ｂｅｔｔｉ亏数ξ（犌）≤４,因此有犌的最大亏格γ犕（犌）≥ １２β（犌）－２．     

在VLSI布局中的Boole方法

用Boole方法,讨论那些与VLSI布局有关的图的嵌入,主要是在图的平面性一般理论、可定向性以及纵横布局等方面,似有异曲同工之妙.     

曲面上构造三次3-连通非Hamiltonian地图的一种方法(英文)

Tutte在1946年构造性证明了并非每个简单的3-凸胞腔都是Hamiltonian的后,人们又陆续提出了多种构造三次3-连通非Hamiltonian平面图的方法,但无一能用于在一般曲面上寻找三次3-连通非Hamiltonian地图.本文提出了一种新的构造方法,可在任一个曲面上构造出三次3-连通非Hamiltonian地图.     

图的最大亏格、支配数和围长

一个连图G的最大亏格γM（G）=（β（G）-ξ（G）/2,其中β（G）=E（G）-V（G 1是G的圈秩,ξ（G）是G的Betti亏数,本文利用G的支配数和围长给出了G的Betti亏数ξ（G）的一个上界,从而也给出了最大亏格γ（M（G）的一个下界,而且它是可达的,对于某些图类,该下界比黄元秋（2000）所给下界更好。     

关于(ξ,k)-临界图

设 G为连通图 ,且ξ(G) =k≥ 1 ,若对 G中任意边 e,均有ξ(G\e) =k - 1 ,则称 G为 (ξ,k) -临界图 .本文刻划了ξ- 1 -临界图的若干性质 ,给出了一个图为ξ- 1 -临界图的一些充分或必要条件 ,以及一些ξ- 1 -临界图类 .     

柱面上有根近三角剖分的计数

柱面上的三角剖分是一类与环面上的地图紧密相关的地图．本文提供了一个计算柱面上有根近三角剖分的具有三个变量的精确公式．     

六阶图G与Sn的积图的交叉数

确定图的交叉数是NP．完全问题．目前已确定交叉数的六阶图与星图的笛卡尔积图极少。本文确定了—个六阶图G与星图5k积图的交叉数为Z（6,n）＋2n＋[n/2].     

一类循环图在射影平面上的嵌入北大核心CSCD

嵌入的联树模型是研究图的曲面嵌入的一种有效方法,尤其能方便快捷地研究图在球面,环面,射影平面,Klein瓶上的嵌入。此方法通过合理选择生成树,得到联树和关联曲面,然后对关联曲面进行计数,计算出图在曲面上的嵌入个数.本文利用嵌入的联树模型得出了循环图C(2n+1,2)(n>2)在射影平面上的嵌入个数.