Some Results On The Crossing Numbers Of Some Cartesian Product Graphs

Garey and Johnson (1983) showed that determining the crossing number is anNP-complete problem. Because of its complexity, there are a few exact results onthe crossing numbers of graphs for its complexity. Even in many cases, it is verydifficult to find upper or lower bounds of the crossing numbers of graphs.The proofmethod is closed to the structure of the graphs,even the same method is not suitthe graphs which have the similar structure. In this paper, we study the crossingnumbers of the cartesian products of path and cycle with some 6-vertex graphs.At first, we introduce the background of the crossing number and its devel-opment around the world, the methods of the research and the problems we willsolve.Second, we give some conceptions and properties, and introduce the requiredknowledge including crossing numbers when read this paper.Third, In chapter three, we determine an upper bounds of the crossing numbersof K_3,3×P_n, then analyze its structure in detail,with the induction, we determinethe crossing numbers of K_3,3×P_n. In chapter four, we first determine the crossingnumber of a subgraph of S₅×C_n, because the crossing number of the supergraphis not less than the subgraph,then determine the crossing numbers of S₅×C_n andS₅×S_n.At last, there are some questions when researching into this problem, and thedirection I will go ahead.