特殊二部图的上可嵌入性  

Upper-embeddability of Special Bipartite Graphs

作　　者：吴向群[1] 任韩[1] 吕长青[1] 

机构地区：[1]华东师范大学数学系

出　　处：《华东师范大学学报（自然科学版）》2005年第Z1期85-89,102,共6页Journal of East China Normal University(Natural Science)

基　　金：国家自然科学基金(10271048)上海市重点学科基金上海市基础研究重点项目(04JC14031)

摘　　要：探讨二部图的上可嵌入性,证明了如下结果：(1)设G=(X,Y；E),定义G^3=(V(G^3),E(G^3)),其中V(G^3)=V(G),E(G^3)=E(G)∪{e=xy|d_G(x,y)：3,x∈X,y∈Y},则G^3是上可嵌入的；(2)设G=(X,Y；E),|X|=|Y|=n(n≥3),对任一对d_G(x,y)=3的x∈X,y∈Y,均有d(x)+d(y)≥n+1,则G是上可嵌入的。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) LetG=(X, Y; E) and G^3=(V(G^3), E(G^3)), where V(G^3)=V(G),E(G^3)=E(G)∪J{e=xy|d_G(x,y)=3,x∈X,y∈Y}, then G^3 is up-embeddable; (2)Let G=(X, Y; E),|X|=|Y|=n(n≥3), for every pair of x∈X, y∈Y with d_G(x, y)=3, such that d(x)+d(y)≥n+1, then G is up-embeddable.

关 键 词：最大亏格 BETTI数 二部图 上可嵌入 

分 类 号：O157.5[理学—数学]