The Thickness Of Some Join Graphs

The thickness of the graph G is the minimum number of the planar spanning sub-graphs into which G can be decomposed.It is an important measurement of the planari-ty of a graph and has been widely used in VLSI and network design.The union G?H of two graphs G and H is the graph(V(G)U V(H),E(G)U E(H)).The join G+H of two vertex disjoint graphs G and H is obtained from G?H by joining every vertex of G to every vertex of H.In this paper,we mainly study the thickness of some join graphs.In the second Chapter,we study the thickness of the join graph related to the disordered binary tree.By constructing the planar subgraph decomposition of the join graph,the thickness of disordered binary tree with isolated vertex graph (?)n,path Pn and circle Cn are obtained.When s is even and n>1/2(s-2)2,or s is odd and n>(s-2)(s-1),?(Ts+(?)n)=?(Ts+Pn)=?(Ts+Cn)=[s/2].In Chapter 3,we assume that if G is a simple graph on n vertices.When n is odd and s>(n-2)(n-1),?(G+Ts)=[n+2].When n is even and s>1/2(n-2)2,it has two cases:if[s/2]?n/2,we have ?(G+Ts)=n/2;if[s/2]>n/2,we have ?(G+Ts)?[n/2,n/2+1].In Chapter 4,we mainly study the thickness of the join graph related to complete bipartite graph Kl,m.When l+m is even and n>1/2(l+m-2)2,or l+m is odd and n>(l+m-2)(l+m-1),?(Kl,m+(?)n)=?(Kl,m+Pn)=?(Kl,m+Cn)=?(Kl,m+Ts)=[l+m/2].In Chapter 5,we obtain the thickness of the join graph Kp1,p2,…,pk+Ts.When ?i=1k pi is odd and (?).When (?) is even and (?),it has two cases:if(?),we have (?),we have (?).