On The Crossing Numbers Of Some Special Graphs

The crossing number of graphs is a vital concept in morden graph theory.Its application is important not only in theory,but also in practice.Then it has attractted many graph theory experts to study.We have already known that to determine the crossing numbers of graphs is NP-complete.Because of its difficulty,at present the classes of graphs whose crossing numbers have been determined are very scarce, and there are only some special graphs whose crossing numbers are known.Even in some cases,it is very difficult to find the upper or lower bounds of the crossing numbers of graphs.In this paper,we study the crossing numbers of the Cartesian products of paths with some special graphs such as the complete bipartite graph K2,m,and the circular graph C(8,2),and we discuss the crossing numbers of the join,at last we obtain the toroidal crossing number of K4,n.At first,in Chapter one,we introduce the backgrouds and origins of the crossing number and its developments and recent situations around the world,and present the meanings of the research and the problems which we wil solve.In Chapter two,we give some conceptions and properties of the crossing number, and introduce the required knowledges while reading this paper.In Chapter three,we determine the crossing numbers of the Cartesian products of paths Pn with the complete bipartite graph K2,m and the circular graph C(8,2).In Chapter four,we discuss the crossing number of the join.On one hand,we get the crossing number of the join of cycles Cm and paths P,n if the Zarankiewicz's conjecture is hold;on the other hand,we determine the crossing number of the join of the class of special graphs and one vertex.In Chapter five,we study how to draw a graph in the toms,and calculate the toroidal crossing number of the complete bipartite K4,n. In the last chapter,we intruduce the directions of our research work and put forward some relative problems which we will go ahead.