Researches On The Crossing Numbers Of Some Graphs

The crossing number of graphs comes from the Pual Tur(?)n's brick factory problem during the World WarⅡ, and it becomes a very active branch in Graph Theory, many authors have studied this area. However, determining the crossing number of graphs is NP-complete. Because of its difficulty, there are only very scarce special classes of graphs whose crossing numbers are determined. Even in some cases, it is very difficult to find the upper or lower bounds of the crossing number of graphs. In this paper, we study the crossing number of some special graphs, such as the generalized Petersen graph P(3k,k), the circulant graph C(3k-1;{1,k}), the Cartesian product of S_n with two special 6-vertex graphs, W_m×P_n,S_m∨P_n,S_m∨C_n,etc. The paper is consist of 9 chapters:In chapter one, we introduce the origins and backgrounds of the crossing number, its theorical and practical meanings, and its development around the world.Chapter two gives some conceptions and properties of the crossing number, and introduces the required knowledge for reading this paper.Chapter three determines that the crossing number of the generalized Petersen graph P(3k,k) is k for arbitrary k≥4.Chapter four studies the upper and lower bounds of the crossing number of the circulant graph C(3k-1;{1, fe}) for k≥3.Chapter five investigates the crossing number of Cartesian product of the wheel W_m with path P_n for m≥3 and n≥1.In chapter six, the crossing numbers of the Cartesian product of S_n with two special 6-vertex graphs are determined.Chapter seven studies the crossing numbers of S_m∨P_n for m= 3,4,5 and for all n, and the crossing numbers of S_m∨C_n for m = 3,4 and for all n.Chapter eight investigates the general property of the crossing number of graphs, and presents a sufficient condition to enforce a good drawing to be optimal. In the last chapter, we make some conclusions of our research work and put forward some relative problems which we will go ahead.