Journal of East China Normal University(Natural Sc ›› 2006, Vol. 2006 ›› Issue (5): 66-71.

• Article • Previous Articles     Next Articles

Maximum Genus and 1-Factors of Near-Triangulation Graphs(Chinese)

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 Published:2006-09-25
  • Contact: REN Han

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: upper-embedding, Betti number, 1-factor, near-triangulation, maximum genus, upper-embedding, Betti number, 1-factor, near-triangulation

CLC Number: