Journal of East China Normal University(Natural Sc ›› 2005, Vol. 2005 ›› Issue (5/6): 85-89,1.

• Article • Previous Articles     Next Articles

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

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

CLC Number: