Journal of East China Normal University(Natural Sc ›› 2006, Vol. 2006 ›› Issue (3): 37-43.

• Article • Previous Articles     Next Articles

Classes of Upper Embeddable Graphs with Specific Minimum Degree-Sum of Vertices in Independent-Set(English)

GAO Yan-bo1,2, REN Han1   

  1. 1. Department of Mathematics, East China Normal University, Shanghai 200062, China; 2. School of Science, Nantong University, Nantong Jiangsu 226007, China
  • Received:2004-04-19 Revised:2004-07-20 Online:2006-05-25 Published:2006-05-25
  • Contact: REN Han

Abstract: Combined with the edge-connectivity, this paper investigated the upper embeddable graphs with specific minimum degree-sum of vertices in its independent-set, and obtained the following results. (1) Let G be a 2-edge-connected simple graph, if G satisfies the following conditions: for any 3-independent set I in G, ∨xi ,xjI (i,j = 1,2,3), d(xi ,xj)≧3 (1 ≦ i j ≦ 3) =>
i = 13 d(xi) ≧ v + 1(v = | V(G)|}), then G is upper embeddable; (2) Let G be
3-edge-connected simple graph, if G satisfies the following conditions: for any 6-independent set I in G, ∨xi ,xjI (1≦i,j≦6), d(xi,xj) ≧3(1 ≦ i j ≦ 6) => ∑i = 16 d(xi) ≧ v + 1(v = | V(G)|), then G is upper embeddable.

Key words: maximum genus, Betti deficiency, upper embeddable, k-independentset, Graph, maximum genus, Betti deficiency, upper embeddable, k-independentset

CLC Number: