华东师范大学学报(自然科学版) ›› 2006, Vol. 2006 ›› Issue (3): 37-43.

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

独立集中具有最小特定度和的点的上可嵌入图类(英)

高岩波1,2, 任 韩1   

  1. 1. 华东师范大学 数学系, 上海 200062;2. 南通大学 理学院, 江苏 南通 226007
  • 收稿日期:2004-04-19 修回日期:2004-07-20 出版日期:2006-05-25 发布日期:2006-05-25
  • 通讯作者: 任 韩

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

摘要: 结合边连通度,探讨了独立集中具有最小特定度和的点的上可嵌入图.得到了下列结果. (1)设G,是一个2-边连通简单图且满足条件:对任意一个G的3-独立集I, ∨xi ,xjI (i,j = 1,2,3), d(xi ,xj)≧3 (1 ≦ i j ≦ 3) =>∑i = 13 d(xi) ≧ v + 1(v = | V(G)|}), 则G是上可嵌入的;(2)设G是一个3-边连通简单图且满足条件:对任意一个G的6-独立集I, ∨xi ,xjI (1≦i,j≦6), d(xi,xj) ≧3(1 ≦ i j ≦ 6) => ∑i = 16 d(xi) ≧ v + 1(v = | V(G)|), 则G是上可嵌入的.

关键词: 图, 最大亏格, Betti亏数, 上可嵌入的, k-独立集, 图, 最大亏格, Betti亏数, 上可嵌入的, k-独立集

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

中图分类号: