梯型图和交叉型图的亏格分布

提供了求梯型图和交叉型图的亏格分布显式表达式的方法. 作为一个例子, 求出了第1类亏格依赖于边数的图类 $J_n$的亏格分布的显式表达式.     

一般梯图的亏格分布

本文求出了-些曲面集的亏格分布的显式表达式.在联树的基础上,通过运用曲面分类法把一般梯图的亏格分布转化为这些曲面集的线性组合,从而可求出它们的显式表达式.     

一类图的亏格

在刘提出的联树模型的基础上,更广泛未必具有对称性的图类的亏格问题可以得到解决．本文中,我们得到了一类具有比较弱对称性的新图类的亏格．作为推论亦得到了完全三部图Kn,n,l（l≥n≥2）的亏格．此处所用方法比已知用来计算图的亏格问题的方法,如电流图等,更直接且可用线性时间算法实现．     

两类四正则图的完全亏格分布

一个图G的完全亏格多项式表征了图G的亏格(可定向,不可定向)分布情况.本文利用刘彦佩提出的嵌入的联树模型,得出了两类新的四正则图的完全亏格多项式,并推导出已有结果的两类图的完全亏格多项式.此处的结果形式更为简单.     

扇图在曲面上嵌入的分类

图在曲面上嵌入的分类就是确定图在同一曲面上(不等价的)嵌入的数目.本文,利用刘彦佩提出的嵌入的联树模型,得到了双极图与扇图的关联曲面之间的关系,进而由已知结论的双极图的亏格分布和完全亏格分布推导出扇图的亏格分布和完全亏格分布,并给出了扇图在亏格为1-4的不可定向曲面上嵌入的个数的显式.     

循环图C(2n,2)(n＞2)在射影平面上的嵌入计数

图在球面上的嵌入个数即柔性问题已经由刘彦佩教授解决,研究图在射影平面上的嵌入亦有着重要的意义。本文利用刘彦佩教授创建的嵌入联树模型得出了循环图C(2n,2)(n>2)在射影平面上的嵌入个数。     

叉梯有向图在可定向曲面上的亏格多项式

虽然一些关于图的亏格分布的结果已经知道,但关于有向图的结果却很少.本文第二作者发现了计算图的嵌入多项式的联树法,这篇文章将此方法推广到计算有向图的嵌入多项式.得到了一类新的四正则叉梯有向图在可定向曲面上的亏格多项式.这些结果为解决Bonnington提出的第三个问题奠定了基础.     

有向图在可定向曲面上的嵌入性

Bonnington,Conder和Morton在2002年给出了有向图嵌入亏格的基本性质,并提出了如下问题:如何刻划有向嵌入是上可嵌入的?是否存在类似刻划图的上可嵌入中使用的叮裂树的结果?受此问题的启发,收稿给出了一类有向图在可定向曲面上是上可嵌入的性质.作为直接推论,可得到已有的反棱境图是上可嵌入的结论.另外得到了一些新的上可嵌入的图类.     

串联双路图的亏格分布

计算双路图的亏格分布是拓扑图论关注的一个问题,利用传递矩阵与向量积矩阵,给出了两类由双路图串联构建而成的两类闭链图的亏格分布.     

Genus distribution of ladder type and cross type graphs

In this paper a method is given to calculate the explicit expressions of embedding genus distribution for ladder type graphs and cross type graphs. As an example, we refind the genus distribution of the graph J _n which is the first class of graphs studied for genus distribution where its genus depends on n. This work was supported National Natural Science Foundation of China (Grant Nos. 10571013, 60433050) and the State Key Development Program of Basic Research of China (Grant No. 2004CB318004)     

The genus of a type of graph

Based on the joint tree model introduced by Liu, the genera of further types of graphs not necessary to have certain symmetry can be obtained. In this paper, we obtain the genus of a new type of graph with weak symmetry. As a corollary, the genus of complete tripartite graph K n,n,l (l≥n≥2) is also derived. The method used here is more direct than those methods, such as current graph, used to calculate the genus of a graph and can be realized in polynomial time.     

多重圈梯图在射影平面上的嵌入个数

图在不同亏格曲面上的嵌入个数常常有相关关系,因此,分析一些图类在小亏格曲面上的嵌入个数对最终确定图的亏格分布和完全亏格分布有着重要意义,本文利用嵌入的联树模型得出了多重圈梯图在射影平面上的嵌入个数.     

项链图在曲面上的嵌入

Gross,Klein和Rieper(1993)计算了项链图的亏格分布,其后,Chen,Liu和Wang(2006)以及Yang,Liu(2007)分别给出了项链图嵌入分布的递推式和显式.本文给出项链图嵌入分布的多项式显式.从计数角度,此式比上述两个表达式更为简洁.     

Genus Distribution for Circular Ladders

§ 1.Ｉｎｔｒｏｄｕｃｔｉｏｎ　Ｉｎｔｏｐｏｌｏｇｉｃａｌｇｒａｐｈｔｈｅｏｒｙ ,ａｇｒａｐｈｍａｙｈａｖｅｍｕｌｔｉｐｌｅａｄｊａｃｅｎｔｉｅｓａｎｄｓｅｌｆｌｏｏｐｓ.Ａｇｒａｐｈｉｓｃａｌｌｅｄｓｉｍｐｌｉｃｉａｌｉｆｉｔｈａｓｎｏｍｕｌｔｉｐｌｅａｄｊａｃｅｎｃｉｅｓａｎｄｓｅｌｆｌｏｏｐｓ .Ａｓｕｒｆａｃｅｈｅｒｅｉｓａｃｏｍｐａｃｔ2 ｍａｎｉｆｏｌｄｗｉｔｈｏｕｔｂｏｕｎｄａｒｙ .Ａｎｅｍｂｅｄｄｉｎｇｏｆａｇｒａｐｈｉｓｃｅｌｌｕｌａｒｉｆｅａｃｈｃｏｍｐｏｎｅｎｔｏｆｔｈｅｓｕｒ…     

Families of Dot-Product Snarks on Orientable Surfaces of Low Genus

We introduce a generalized dot product and provide some embedding conditions under which the genus of a graph does not rise under a dot product with the Petersen graph. Using these conditions, we disprove a conjecture of Tinsley and Watkins on the genus of dot products of the Petersen graph and show that both Grünbaum’s Conjecture and the Berge-Fulkerson Conjecture hold for certain infinite families of snarks. Additionally, we determine the orientable genus of four known snarks and two known snark families, construct a new example of an infinite family of snarks on the torus, and construct ten new examples of infinite families of snarks on the 2-holed torus; these last constructions allow us to show that there are genus-2 snarks of every even order n ≥ 18.     

Maximum Genus of Strong Embeddings

The strong embedding conjecture states that any 2-connected graph has a strong embedding on some surface. It implies the circuit double cover conjecture: Any 2-connected graph has a circuit double cover.Conversely, it is not true. But for a 3-regular graph, the two conjectures are equivalent. In this paper, a characterization of graphs having a strong embedding with exactly 3 faces, which is the strong embedding of maximum genus, is given. In addition, some graphs with the property are provided. More generally, an upper bound of the maximum genus of strong embeddings of a graph is presented too. Lastly, it is shown that the interpolation theorem is true to planar Halin graph.