On The Crossing Numbers Of Some Classes Graphs

We have already known that determing the crossing numbers of graphs is NP-complete (see [1]). There are a few exact results on the crossing numbers of graphs for its complexity. Even in many cases, it is very difficult to find 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 6-vertex graphs, and if the Zarankiewicz's conjecture is hold, we get the crossing numbers of the complete tripartite graph K_1,10,n, and obtain the crossing number of K_1,m,n when m, n are both even integers.In chapter one, we introduce the backgrouds of the crossing number and its development around the world, the meanings of the research and the problems we wil solve.In chapter two, we give some conceptions and properties, and introduce the required knowledges including crossing numbers when read this paper.In chapter three, we determine the crossing numbers of the cartesian products of paths P_n with some 6-vertex graphs.In chapter four, we get the crossing number of the complete tripartite graph K_1,10,n if the Zarankiewicz's conjecture is hold for m = 11, and we obtain the crossing number of K_1,m,n when n is even integers, if the Zarankiewicz's conjecture is true for K_1+m,,n when m is even integers no more than n.In chapter five, there are some questions when researching into this problem, and the direction I will go ahead.