考察了平面近三角剖分图的最大亏格与独立边集之间的关系．设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是上可嵌入的．作为应用．证明了几个已知的结果．展开更多
A near-triangulation is such a connected planar graph whose inner faces are all triangles but the outer face may be not. Let G be a near-triangulation of order n and C be an SCDC (small circuit double cover)[2] of G. ...A near-triangulation is such a connected planar graph whose inner faces are all triangles but the outer face may be not. Let G be a near-triangulation of order n and C be an SCDC (small circuit double cover)[2] of G. Let Then, C0 is said to he an equilibrium SCDC of G. In this paper, we show that if G is an outer planar graph, δ(C0)≤2, otherwiseδ(C0) ≤4.展开更多
文摘考察了平面近三角剖分图的最大亏格与独立边集之间的关系．设G*是平面近三角剖分图G的一个平面嵌入的几何对偶,如果G*有[1/2φ]个独立边集,那么图G的最大亏格γM(G)≥[1/2β(G)]-11,这里φ和β(G)分别表示图G在平面上嵌入的面数与G的Betti数．特别地,如果φ=0 mod 2,即G有1-因子,则G是上可嵌入的．作为应用．证明了几个已知的结果．
基金Supported by the National Natural Science Foundation of China (69973001)
文摘A near-triangulation is such a connected planar graph whose inner faces are all triangles but the outer face may be not. Let G be a near-triangulation of order n and C be an SCDC (small circuit double cover)[2] of G. Let Then, C0 is said to he an equilibrium SCDC of G. In this paper, we show that if G is an outer planar graph, δ(C0)≤2, otherwiseδ(C0) ≤4.
