灯笼图的可定向嵌入亏格分布

本文主要利用联树法研究了图的亏格多项式,得到了一类新图(灯笼图)的嵌入亏格分布.证明了灯笼图和偶梯图的亏格分布具有相同的递推关系,从而得到了灯笼图的嵌入亏格分布的精确解.     

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

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

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.     

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

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

串联双路图的亏格分布

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

Genus Distribution for Circular Ladders

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

Exponentially many maximum genus embeddings and genus embeddings for complete graphs

There are many results on the maximum genus, among which most are written for the existence of values of such embeddings, and few attention has been paid to the estimation of such embeddings and their applications. In this paper we study the number of maximum genus embeddings for a graph and find an exponential lower bound for such numbers. Our results show that in general case, a simple connected graph has exponentially many distinct maximum genus embeddings. In particular, a connected cubic graph G of order n always has at least distinct maximum genus embeddings, where α and m denote, respectively, the number of inner vertices and odd components of an optimal tree T. What surprise us most is that such two extremal embeddings (i.e., the maximum genus embeddings and the genus embeddings) are sometimes closely related with each other. In fact, as applications, we show that for a sufficient large natural number n, there are at least many genus embeddings for complete graph K _n with n ≡ 4, 7, 10 (mod12), where C is a constance depending on the value of n of residue 12. These results improve the bounds obtained by Korzhik and Voss and the methods used here are much simpler and straight. This work was supported by the National Natural Science Foundation of China (Grant No. 10671073), Science and Technology commission of Shanghai Municipality (Grant No. 07XD14011) and Shanghai Leading Academic Discipline Project (Grant No. B407)     

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.     

不可定向曲面上的最大亏格嵌入和最小亏格嵌入

研究了不可定向曲面上最大亏格嵌入的估计数,得到了几类图的指数级不可定向最大亏格嵌入的估计数的下界.利用电流图理论,证明了完全图K_(12s)在不可定向曲面上至少有2~(3s-1)个最小亏格嵌入;完全图K_(12s+3)在不可定向曲面上至少有2~(2s)个最小亏格嵌入;完全图K_(12s+7)在不可定向曲面上至少有2~(2s+1)个最小亏格嵌入.     

The genus distributions for a certain type of permutation graphs in orientable surfaces

A circuit is a connected nontrivial 2-regular graph.A graph G is a permutation graph over a circuit C,if G can be obtained from two copies of C by joining these two copies with a perfect matching.In this paper,based on the joint tree method introduced by Liu,the genus polynomials for a certain type of permutation graphs in orientable surfaces are given.     

The orientable genus of some joins of complete graphs with large edgeless graphs

In an earlier paper the authors showed that with one exception the nonorientable genus of the graph with m≥n−1, the join of a complete graph with a large edgeless graph, is the same as the nonorientable genus of the spanning subgraph . The orientable genus problem for with m≥n−1 seems to be more difficult, but in this paper we find the orientable genus of some of these graphs. In particular, we determine the genus of when n is even and m≥n, the genus of when n=2^p+2 for p≥3 and m≥n−1, and the genus of when n=2^p+1 for p≥3 and m≥n+1. In all of these cases the genus is the same as the genus of K_m,n, namely ⌈(m−2)(n−2)/4⌉.     

Genus polynomials of cycles with double edges

Two cellular embeddings i: G → S and j: G → S of a connected graph G into a closed orientable surface S are equivalent if there is an orientation-preserving surface homeomorphism h: S → S such that hi = j. The genus polynomial of a graph G is defined by

循环图C(n,m)}的最小亏格

本文给出了所有循环图的可定向与不可定向最小亏格. 同时, 也给出了部分循环图的强最小亏格.     

极大外平面图的不可定向强最大亏格

强嵌入猜想称:任意2-连通图都可以强嵌入到某一曲面上．本文通过分析极大外平面图的结构以及强嵌入的特征,讨论了该图类的不可定向强最大亏格,并给出了一个复杂度为O(nlogn)的算法．其中部分图类的强最大亏格嵌入提供该图的一个少双圈覆盖．     

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

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

平面Halin图的强最大亏格

本文给出了平面Halin图的可定向与不可定向强最大亏格．     

A Lower Bound for the Sectional Genus of Quasi-Polarized Surfaces

Let (X,L) be a quasi-polarized variety, i.e. X is a smooth projective variety over the complex numbers and L is a nef and big divisor on X. Then we conjecture that g(L) = q(X), whereg(L) is the sectional genus of L and . In this paper, we treat the case . First we prove that this conjecture is true for , and we classify (X,L) withg(L)=q(X), where is the Kodaira dimension of X. Next we study some special cases of .     

The Canonical Genus of a Classical and Virtual Knot

A diagram D of a knot defines the corresponding Gauss Diagram G _D . However, not all Gauss diagrams correspond to the ordinary knot diagrams. From a Gauss diagram G we construct closed surfaces F _G and S _G in two different ways, and we show that if the Gauss diagram corresponds to an ordinary knot diagram D, then their genus is the genus of the canonical Seifert surface associated to D. Using these constructions we introduce the virtual canonical genus invariant of a virtual knot and find estimates on the number of alternating knots of given genus and given crossing number.