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

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

关于3-正则图的消圈数和点荫度的一个注记（英文）

本文从图的嵌入角度考虑,给出了一个计算3-正则图的消圈数(见[J.Graph Theory,1997,25(1):59-77])的新公式.结合所得消圈数公式和Xuong的最大亏格定理(见[J.Combin.Theory Ser.B,1979,26(2):217-225]),进而得到了3-正则图的点荫度为2,此结果证明了Raspaud和王维凡在文献[European J.Combin.,2008,29(4):1064-1075]中给出的下列猜想:任何没有3-圈的平面图都有一个顶点的划分(V_1,V_2)使得V_1是独立集,V_2诱导一个森林.     

关于Faudree—Schelp定理的改进

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

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.     

3类特殊图的优美性

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

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

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

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

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

某些曲面上有根近-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.     

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

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