Research On The Crossing Numbers Of Graphs

Since the introductory investigation of crossing numbers of graphs by Paul Turan in early 1970's,the studying on the crossing numbers of graphs have become a very active field gradually in the world.It attracted a large number of international mathematicians and computer scientists to concern about,in particular,a lot of graph theory experts conducted in-depth studies in this area.But,M.R.Garey et al [1]have proven that to determine the crossing numbers of graphs is NP-complete. At present the classes of graphs whose crossing numbers have been determined are very scarce.It has very broad prospects for the studying.However,beause of its difficulty,there are only slow progress for long time.At present,the studying on the crossing numbers of graphs mainly concentrated in the following two areas:on the one hand,to determine the crossing number of some special classes of graphs:On the other hand,to research the property of the crossing number.This paper mainly determine the crossing numbers of the join of paths P_n with some 5-vertex graphs, and the crossing numbers of the Cartesian products of stars S_n with some 6-vertex graphs.The structure of the paper is as follows.In Chapter one,we introduce the backgrouds and origins of the crossing number and its developments and recent situations around the world,and present the meanings of the reseach and the problems which we will solve.In Chapter two,we give some conceptions and properties of the crossing number ,and introduce the required knowledges while reading this paper.In the Chapter three,we determine the crossing numbers of the join of paths P_n with four 5-vertex graphs.In the Chapter three,we determine the crossing numbers of the Cartesian products of paths P_n with K_2,4. In the last Chapter,we intruduce the directions of our research work and put forward some relative problems which we will go ahead.