Maximum Genus and 1-Factors of Near-Triangulation Graphs
-
摘要: 考察了平面近三角剖分图的最大亏格与独立边集之间的关系.设G*是平面近三角剖分图G的一个平面嵌入的几何对偶,如果G*有[1/2]个独立边集, 那么图G的最大亏格M(G)≧[1/2(G)]-1,这里和(G)分别表示图G在平面上嵌入的面数与G的Betti数. 特别地, 如果=0 mod2 即G有1-因子, 则G是上可嵌入的.作为应用, 证明了几个已知的结果.Abstract: This paper proved that if the geometric dual G*of a near-triangulation plane graph G contains a set of [1/2] independent edges, then the maximum genus M(G) of G is at least [1/2(G)]-1 where and (G)$represent the number of faces of plane G and the Betti number of G. In particular, M(G) = 1/2(G) if =0 mod2. As applications, several known results are presented.
-
Key words:
- maximum genus /
- upper-embedding /
- Betti number /
- 1-factor /
- near-triangulation
-
点击查看大图
计量
- 文章访问数: 1498
- HTML全文浏览量: 5
- PDF下载量: 878
- 被引次数: 0
下载: