特殊二部图的上可嵌入性

摘要

探讨二部图的上可嵌入性,证明了如下结果：(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是上可嵌入的。