The Thickness Of Some Multipartite Graphs And Cartesian Product Graphs

The thickness??G?of a graph G is the minimum number of planar spanning sub-graphs into which G can be decomposed.The thickness of the graph is an important indicator of the planarity of the graph and has important applications in very large scale integrated circuits and network designs.However,because determining the thickness of a graph is NP-hard,only few number of graphs are known for their thickness.This paper mainly study the thickness of some complete multipartite graphs,Cartesian prod-uct graphs,join graphs and Kronecker product graphs as well as the 4-girth thickness of the complete 3-partite graph.In Chapter 1,we introduce concepts and background of the graph thickness prob-lem and the content of each chapter of this thesis.In chapter 2,on the basis of the planar decomposition of the complete 2-partite graph K_n,n,we construct the planar decompo-sition of the complete 3-partite K_1,n,nand K_2,n,nand then we determine their thickness.Furthermore,based on the planar decomposition of complete 3-partite K_2,n,n,we con-struct the planar decomposition of the complete 4-partite graph K_1,1,n,nand obtain the thickness of the complete 4-partite graph K_1,1,n,n.The Cartesian product of graphs G and H is the graph G H whose vertex set is V?G H?=V?G?×V?H?and edge set is E?G H?={?g,h??g^?,h^??|gg^??E?G?and h=h^?,or hh^??E?H?and g=g^?}.In Chapter 3,we study the thickness of some Cartesian product graphs.For most values of n,we obtain the thickness of the Cartesian product of the complete graph K_nand the circle C_m?m?3?as well as the complete 2-partite graph K_n,nand the circle C_m?m?3?.By constructing the planar decomposition of the Cartesian product of the complete 2-partite graph K_n,mand the path P_k?k?2?,we determine the upper and lower bounds of its thickness and the exact value for the thick-ness of the Cartesian product graph of the complete 2-partite graph K_n,mand the path P₂.Subsequently,we get the thickness of the Cartesian product graph of the complete2-partite graph K_n,nand the path P_k?k?2?.The join of graphs G and H,denoted by G+H,in which the vertex set is V?G+H?=V?G??V?H?and the edge set is E?G+H?={?v_i,u_j?|v_i?E?G?,u_j?E?H?}?E?G??E?H?.In Chapter 4,firstly we study the thickness of the join of circles and circles,paths and paths,circles and paths,respectively.Then we study the thickness of the join of an arbitrary graph and circles.The Kronecker product graph G×H of graphs G and H has vertex set V?G×H?=V?G?×V?H?,edge set E?G×H?={?g,h??g^?,h^??|gg^??E?G?and hh^??E?H?}.In Chapter 5,we determine the Kronecker product of the complete graph and the path.The g-girth thickness??g,G?of a graph G is the minimum number of planar sub-graphs whose union is G with the girth of each planar subgraph is at least g.It is a generalization of the usual thickness in which the 3-girth thickness??3,G?is the usu-al thickness??G?.In Chapter 6,we obtain the 4-girth thickness of complete tripartite graph K_n,n,nfor all values of n and the 4-girth thickness of complete graph K₁₀.