华东师范大学学报(自然科学版) ›› 2005, Vol. 2005 ›› Issue (5/6): 85-89,1.

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

特殊二部图的上可嵌入性

吴向群1,2 ,任韩1 ,吕长青1   

  1. 1. 华东师范大学数学系, 上海 200062 ;2. 泉州师院数学系, 福建 362000
  • 收稿日期:2004-01-06 修回日期:2004-03-03 出版日期:2005-12-31 发布日期:2005-12-31
  • 通讯作者: 吴向群

Upper-embeddability of Special Bipartite Graphs(Chinese)

Wu Xiang-qun 1,2, REN Han1, Lü Chang-qing1

  

  1. 1. Department of Mathematics, East China Normal Normal University 200062, China 2. Department of Mathematics,Quanzhou Normal University,Fujian 362000, China
  • Received:2004-01-06 Revised:2004-03-03 Online:2005-12-31 Published:2005-12-31
  • Contact: Wu Xiang-qun

摘要： 探讨二部图的上可嵌入性, 证明了如下结果: (1)设G=(X,Y;E), 定义G3=(V(G3),E(G3)),其中 V(G3)=V(G),E(G3)=E(G)∪{e=xy︱ dG(x,y)=3,x∈ X,y∈ Y},则 G3 是上可嵌入的；(2)设 G=(X,Y;E),|X|=|Y|=n (n≥ 3),对任一对 dG(x,y)=3的x∈ X,y∈ Y, 均有 d(x)+d(y)≥ n+1, 则 G 是上可嵌入的。

关键词: 最大亏格, Betti数, 二部图, 上可嵌入, 最大亏格, Betti数, 二部图, 上可嵌入

Abstract: Liu and Nebesky have independently provided different necessary and sufficient conditions for the upper embeddability of graphs. This paper mainly investigates the upper embeddability of bipartite graphs. We prove the following result:（1）Let G=(X,Y;E)and G3=(V(G3),E(G3)), where V(G3)=V(G),E(G3)=E(G)∪{e=xy|dG(x,y) = 3,x∈ X,y∈ Y}, then G3 is up-embeddable； (2)Let G=(X,Y;E),|X|=|Y|=n(n≥ 3), for every pair of x∈ X,y∈ Y with dG(x,y)=3, such that d(x)+d(y)≥ n+1,then G is up-embeddable.

Key words: Bipartite graph, Bettti deficiency, Upper embeddable, Maximum genus, Bipartite graph, Bettti deficiency, Upper embeddable

中图分类号: