关于图的余树的奇连通分支数的内插定理

本文研究了连通图的余树的奇连通分支数与其可定向嵌入的关系.我们先给出了关于连通图的余树的奇连通分支数的内插定理.作为其应用,我们推广了Xuong和刘彦佩关于图的最大亏格的计算公式,并且证明了如下结果:任意一个连通图G一定满足下列条件之一: (a)对于任意的满足γ(G)≤g≤γM(G)整数g,只要图G嵌入到可定向曲面Sg上,就存在支撑树T,使g-1/2β(G)-ω(T)),其中,γ(G)与γM(G)分别是图G的最小和最大亏格,β(G)与ω(T)分别是图G的Betti数和由T确定的余树的奇连通分支数; (b)对连通图G的任意一个支撑树T,G可以嵌入某个可定向曲面上使其恰好有ω(T) 1个面.特别地,我们给出了所有非平面的3-正则的Hamilton图G所嵌入的可定向曲面的亏格的计算公式.     

可定向曲面上具有较短不可收缩圈图嵌入的唯一性

拓扑图论中的一个基本问题就是要决定图在一个(可定向)曲面上的嵌入之数目(既嵌入的柔性问题).H.Whitney的经典结果表明:一个3-连通图至多有一个平面嵌入;C.Thomassen的LEW-嵌入(大边宽度)理论将这一结果推广到一般的可定向曲面.本文给出了几个关于一般可定向曲面上嵌入图的唯一性定理.结果表明:一些具有大的面迹的可定向嵌入仍然具有唯一性.这在本质上推广了C.Thomassen在LEW-嵌入方面的工作.     

BISINGULAR MAPS ON SOME SURFACES

A map is bisingular if each edge is either a loop (This paper only considersplanar loop) or an isthmus (i.e., on the boundary of the same face). This paper studies thenumber of rooted bisingular maps on the sphere and the torus, and also presents formulaefor such maps with three parameters: the root-valency, the number of isthmus, and thenumber of planar loops.     

图的1-因子数目的递推求法

首先对图的1-因子进行分类,求出每一类1-因子数目的递推关系式;然后对各类1-因子数目的递推式进行求和,得到一组有相互联系的递推关系式;利用递推式之间的相互关系,消去不需要的,得到图的1-因子数目的递推关系式;最后求出此递推式的公式解。     

关于Faudree—Schelp定理的改进

一个图Ｇ＝（Ｖ，Ｅ）是［ｌ，ｍ］－路连通的，如果在Ｇ的任意一对节点ｘ与ｙ之间有长为ｋ－１的路Ｐｋ（ｘ，ｙ），ｋ＝ｌ，ｌ＋１，．．．，ｍ。Ｇ具有性质Ｐ（ｋ），如果对Ｇ的任何一对距离为２的节点ｘ和ｙ，有ｄ（ｘ）＋ｄ（ｙ）≥ｋ。     

某些曲面上有根近-4-正则欧拉迹的计数

In this article the rooted planar near-4-regular Eulerian trails are enumerated and an explicit formula for such maps is presented. Further, the rooted near-4-regular Eulerian maps on the torus are counted in an exact way.     

Strong Embeddings of Outer Planar Near-triangulations on Non-orientable Surfaces

§ 1.Ｉｎｔｒｏｄｕｃｔｉｏｎ　ＦｏｒａｇｒａｐｈＧｗｅｄｅｎｏｔｅｂｙＶ(Ｇ)ａｎｄＥ(Ｇ) ,ｒｅｓｐｅｃｔｉｖｅｌｙ ,ｔｈｅｖｅｒｔｅｘｓｅｔａｎｄｅｄｇｅｓｅｔｏｆＧ ,ｗｉｔｈ |Ｖ(Ｇ) | =ν(Ｇ)ａｎｄ |Ｅ(Ｇ) | =ε(Ｇ) .Ａｇｒａｐｈｗｉｔｈｍｕｌｔｉ ｅｄｇｅａｌｌｏｗａｂｌｅｉｓｃａｌｌｅｄａｍｕｌｔｉ ｇｒａｐｈ .Ａｐｌａｎａｒｇｒａｐｈｉｓｓｕｃｈａｇｒａｐｈｗｈｉｃｈｈａｓａｎｅｍｂｅｄｄｉｎｇ μ(Ｇ)ｏｆｔｈｅｇｒａｐｈｉｎｔｈｅｐｌａｎｅ .ＩｆＧｉｓａｐｌａｎａｒｇｒａｐｈ ,ｗｅｄｅｎ…     

3类特殊图的优美性

用构造的方法给出了I(∧Cn,4),I(Fn,4)和Pn,4的优美标号,证明了I(∧Cn,4),I(Fn,4)和Pn,4都是优美图.     

一个不可定向曲面的极小禁用子图的构造

曲面S的一个极小禁用子图是这样的一个图,它的任何一个顶点的度都不小于3,它不能嵌入在S上,但是删去任何一条边后得到的图能嵌入在S上.本文给出了四种构造一个不可定向曲面的极小禁用子图的方式,即粘合一个顶点,一个图的边被其它的图替换,粘合两个顶点,将一个图放在另一个图的一个曲面嵌入的面内.