Research On The Crossing Numbers Of Cartesian Products For 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.Recently, the crossing numbers of the Cartesian products become more interested.In this paper, we study the crossing numbers of the Cartesian products of G_i(i = 1,2,3,4) and P_n, determine the crossing numbers of the Cartesian products of a $5$-vertices graphs G₁₃ with S_n,and W₅ with S_n.Chapter one, introducing the backgrounds of the crossing numbers of graphs,its development around the world, the meanings of the research, the problems we will solve,and giving some conceptions and properties.Chapter two,determining the crossing numbers of the Cartesian products of G_i(i =1,2,3,4) with P_n.Chapter three, determining the crossing numbers of the Cartesian products of a 5-vertices graphs G₁₃ with S_n.Chapter four, determining the crossing numbers of the Cartesian products of W₅ with S_n.Chapter five, describing some questions when researching into this problem, and the direction I will go ahead.