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...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 $ (\sqrt 2 )^{m + n + \tfrac{\alpha } {2}} $ 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 $ C2^{\tfrac{n} {4}} $ 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.展开更多
It is known (for example see [2]) that the maximum genus of a graph is mainly determined by the Betti deficiency of the graph. In this paper, the authors establish an upper bound on the Betti deficiency in terms of th...It is known (for example see [2]) that the maximum genus of a graph is mainly determined by the Betti deficiency of the graph. In this paper, the authors establish an upper bound on the Betti deficiency in terms of the independence number as well as the girth of a graph, and thus use the formulation in [2] to translate this result to lower bound on the maximum genus. Meantime it is shown that both of the bounds are best possible.展开更多
考察了平面近三角剖分图的最大亏格与独立边集之间的关系．设G*是平面近三角剖分图G的一个平面嵌入的几何对偶,如果G*有[1/2φ]个独立边集,那么图G的最大亏格γM(G)≥[1/2β(G)]-11,这里φ和β(G)分别表示图G在平面上嵌入的面数与G的Be...考察了平面近三角剖分图的最大亏格与独立边集之间的关系．设G*是平面近三角剖分图G的一个平面嵌入的几何对偶,如果G*有[1/2φ]个独立边集,那么图G的最大亏格γM(G)≥[1/2β(G)]-11,这里φ和β(G)分别表示图G在平面上嵌入的面数与G的Betti数．特别地,如果φ=0 mod 2,即G有1-因子,则G是上可嵌入的．作为应用．证明了几个已知的结果．展开更多
Let G be a simple graph of order n and girth g. For any two adjacent vertices u and v of G, if d G (u) + d G (v) ? n ? 2g + 5 then G is up-embeddable. In the case of 2-edge-connected (resp. 3-edge-connected) graph, G ...Let G be a simple graph of order n and girth g. For any two adjacent vertices u and v of G, if d G (u) + d G (v) ? n ? 2g + 5 then G is up-embeddable. In the case of 2-edge-connected (resp. 3-edge-connected) graph, G is up-embeddable if d G (u) + d G (v) ? n ? 2g + 3 (resp. d G (u) + d G (v) ? n ? 2g ?5) for any two adjacent vertices u and v of G. Furthermore, the above three lower bounds are all shown to be tight.展开更多
基金the National Natural Science Foundation of China (Grant No. 10671073)Scienceand Technology commission of Shanghai Municipality (Grant No. 07XD14011)Shanghai Leading AcademicDiscipline Project (Grant No. B407)
文摘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 $ (\sqrt 2 )^{m + n + \tfrac{\alpha } {2}} $ 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 $ C2^{\tfrac{n} {4}} $ 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.
基金National Natural Science Foundation of China!(No.19801013).
文摘It is known (for example see [2]) that the maximum genus of a graph is mainly determined by the Betti deficiency of the graph. In this paper, the authors establish an upper bound on the Betti deficiency in terms of the independence number as well as the girth of a graph, and thus use the formulation in [2] to translate this result to lower bound on the maximum genus. Meantime it is shown that both of the bounds are best possible.
文摘考察了平面近三角剖分图的最大亏格与独立边集之间的关系．设G*是平面近三角剖分图G的一个平面嵌入的几何对偶,如果G*有[1/2φ]个独立边集,那么图G的最大亏格γM(G)≥[1/2β(G)]-11,这里φ和β(G)分别表示图G在平面上嵌入的面数与G的Betti数．特别地,如果φ=0 mod 2,即G有1-因子,则G是上可嵌入的．作为应用．证明了几个已知的结果．
基金supported by National Natural Science Foundation of China (Grant No. 10571013)
文摘Let G be a simple graph of order n and girth g. For any two adjacent vertices u and v of G, if d G (u) + d G (v) ? n ? 2g + 5 then G is up-embeddable. In the case of 2-edge-connected (resp. 3-edge-connected) graph, G is up-embeddable if d G (u) + d G (v) ? n ? 2g + 3 (resp. d G (u) + d G (v) ? n ? 2g ?5) for any two adjacent vertices u and v of G. Furthermore, the above three lower bounds are all shown to be tight.
