On The Crossing Numbers Of Some Classes Graphs

The crossing number of graphs is a vital concept in modern graph theory. Its application is important not only in theory,but also in practice.Then it has attracted many graph theory experts to study.We have already known that to determine the crossing numbers of graphs is NP-complete.Because of its difficulty, at present the classes of graphs whose crossing numbers have been determined are very scarce,and there are only some special graphs whose crossing numbers are known.Even in some cases,it is very difficult to find the upper or lower bounds of the crossing numbers of graphs.In this paper,we study the crossing numbers of the Cartesian products of stars with some 6-vertex graphs,and we discuss the crossing numbers of the join.At first,in Chapter one,we introduce the backgrounds and origins of the crossing number and its developments and recent situations around the world,and present the meanings of the research and the problems which we will solve.In Chapter two,we give some conceptions and properties of the crossing number, and introduce the required knowledge while reading this paper.In Chapter three,we determine the crossing numbers of the Cartesian products of stars S_n with several 6-vertex graphs.In Chapter four,we discuss the crossing number of the join.We get the crossing number of the join of paths P_n with some 6-vertex graphs.In the last chapter,we introduce the directions of our research work and put forward some relative problems which we will go ahead.