The Investigation On The Crossing Numbers Of The Join Graphs And Cartesian Product 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 attract-ted many graph theorist to study. We have already known that to determination of the crossing numbers for 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 graphs, and we discuss the crossing numbers of the join. This paper is consist of four chapters:At first, in Chapter one, we introduce the backgrouds, the origins of the crossing number, the developments and recent situations around the world, and present the meanings of the research and the problems which we will 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 discuss the crossing number of the join.On one hand,we determine the crossing number of the join of some 5-vertex graphs and some 5-vertex graphs and paths P_n if the Zarankiewicz's conjecture is hold; on the other hand ,we give the crossing number of S_m∨P_n.In Chapter four, we determine the crossing numbers of the Cartesian products of star S_n with some special 6-vertex graphs.In Finally, we intruduce the directions of our research work and put forward some relative problems which we will go ahead.