On The Crossing Numbers Of Graph

Determing the crossing numbers of graphs has proved to be NP-complete. There are a few exact results on the crossing numbers of graphs class because of its complexity. In many cases,even it is very difficult to find out good bounds of the crossing numbers of graphy .Now,many articls are focus on investigating the crossing numbers of complete graphs, complete bipartite graphs ,complete tripartite graphs ,cyclic-order graghs and some special graph's cartesian products graphs,and so on. In this paper ,we study the crossing numbers of the cartesian product graph and complete tripartite graph.In chapter one,we give the conception of crossing number ,some interrelated conception and some interrelated character on the crossing number.In chapter two ,we determine the crossing number of the cartesian product of five graphs on 6-vertex with path.In chapter three, we determine the crossing numbers of the cartesian products of S₅ and 5 graphs on 6-vertex with path P_n.In chapter four,we determine the crossing number of the the complete tripartite graph cr(K_1,m,n , Where S₅.,S_n and P_n are the star with five edges,n edges and the path with n edges ,respectively.