The Crossing Numbers Of Cartesian Products Of A Class Of Graphs

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 graphs .Now,many articles 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 of a class of graphs.In chapter one,we introduce the backgroud of the crossing number and it's development around the world.In chapter two,we give the conception of crossing number ,some interrelated conception and some interrelated character on the crossing number.In chapter three,we give an upper bound on the crossing numbers of P_m × W_n that isand determined the crossing number of P₁ × W_n, P₂ × W_n and P₃ × W_n ,respectively. Here,P_n is the path of length n. W_n is a suspension to C_n and C_n is the circle of length n.In chapter four, we determine the crossing numbers of the cartesian products of some graphs on 6-vertex with path P_n.