On The Crossing Numbers Of Graphs

The crossing number of a graph is a very important concept in Graph Theory. It is has both theoritical and pratical meanings, and it has been applied to many areas, such as the VSLI problem, etc.It is known that determining the crossing numbers of graphs is NP-complete (see[1]). There are only a few results on the crossing numbers of graphs for its complexity. In this paper, firstly, we introduce some backgrounds. Then we prove the crossing numbers of S₃×W_n and W₄×S_n in chapter two and three, respectively. In chapter four, the crossing number of the Cartesian product of a 6-vertices graphs with S_n is determined. And we prove that cr(K_3,n\e) and cr(K_4,n\e) in chapter five.