华东师范大学学报(自然科学版) ›› 2006, Vol. 2006 ›› Issue (5): 66-71.

• 数学 统计学 • 上一篇    下一篇

近三角剖分图的最大亏格与1-因子

吕长青1,2, 任 韩1   

  1. 1. 华东师范大学 数学系, 上海 200062; 2. 枣庄学院 数学系, 山东 枣庄 277160
  • 收稿日期:2005-01-07 修回日期:2005-03-18 出版日期:2006-09-25 发布日期:2012-11-27

Maximum Genus and 1-Factors of Near-Triangulation Graphs

LU Chang-qing1,2, REN Han1   

  1. 1. Department of Mathematics, East China Normal University, Shanghai } 200062, China 2. Department of Mathematics, Zaozhuang University, Zaozhuang Shandong 277160, China
  • Received:2005-01-07 Revised:2005-03-18 Online:2006-09-25 Published:2012-11-27

摘要： 考察了平面近三角剖分图的最大亏格与独立边集之间的关系.设G*是平面近三角剖分图G的一个平面嵌入的几何对偶,如果G*有[1/2φ]个独立边集, 那么图G的最大亏格γM(G)≧[1/2β(G)]-1,这里φ和β(G)分别表示图G在平面上嵌入的面数与G的Betti数. 特别地, 如果φ=0 mod2 即G有1-因子, 则G是上可嵌入的.作为应用, 证明了几个已知的结果.

关键词: 最大亏格, 上可嵌入, 1-因子, Betti 数, 近三角剖分图 ,  ,

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  ,

中图分类号: