Study Of The Crossing Numbers For Some Class Graphs

The crossing number was firstly introduced in?Journal of Graph Theo-ry?by Pual Turan in 1944,as an important topological invariant of graphs.It is used to measure how far a graph away from the planar graph.Its theory has been applied in many fields,such as layout problem in the VLSI in large scale circuit,the repaint and identification of sketch,and the graphical representa-tion of DNA in biology engineering and so on.Since the last century,many famous scholars at home and abroad have engaged in the investigation on this field.For example:C.Thomassen,B.Mohar,D.Archdeacon,R.B.Richer,D.J.Kleitman,K.Asano,D.Bokal,P.T.Ho,M.Klesc and domestic Professor Liu Yanpei,and so on.However,M.R.Garey and D.S.Johnson have proven that calculating the crossing number of the general graphs is NP-complete.Because of its difficulty,the results concerning crossing number of the graph aren't very rich,and the classes of graphs whose the crossing numbers can be determined have special structures,which makes that many of methods can't be general-ized to general graphs.In this paper,we try to apply some new methods to explore the crossing numbers of some graph classes.Several results are derived as follows:1.The crossing number of join of some graphs is studied.In the second chapter,for some graphs on five or six vertices,we give the crossing numbers of its join with n isolated vertices as well as with the path Pn on n vertices and with the cycle Cn by using the method different from M.Klesc's.Up to now,there are only few results concerning that.2.The crossing number of Cartesian products of some graphs is studied.In the third chapter,we give the crossing numbers of the Cartesian products of path with some graphs of order 6,7 or even 8 by introducing the "zip product"method.The relationship of crossing number for K2,5?Sn and K2,5,n is es-tablished by introducing some new contraction operations.Thus,we partially solved the conjecture of cr(K2,m?Sn)=cr(K2,m,n)+n[m/2][m-1/2](m?5).3.The crossing numbers of some special graphs are studied.In the forth chapter,for some special graphs on Km-3e,Km n-2e,and K2,m,n,we give the crossing numbers of these graphs.