Studies On The Crossing Numbers Of Two Join Graphs

The crossing number is an important parameter to measure the distance of a graph from the planar graph,and it is also a very significant topological property of a graph.It originated from a practical problem that Pal Turan,a Hungarian mathematician,encountered at a Budapest brick factory during world war ?.Since the concept was proposed,it has been widely used in the field of urban road planning,electronic circuit board design and CAD,etc.Therefore,the theory has attracted extensive attention and in-depth research at home and abroad,and has become a very active research direction in the field of graph theory.Because of the relatively large difficulty,M.R.Garey and D.S.Johnson have proved that determining the crossing number of a graph is a NP-complete problem.Therefore,it is still worth studying the problem of the crossing number of graphs.Up to now,the research results of the crossing number of graphs mainly focus on the special graph classes and most of them cannot be generalized in the general case.In this paper,we will study the crossing number problem of join graph which is a typical graph class.By observing the structural features of graphs,this paper mainly uses mathematical methods such as proof by contradiction and mathematical in-duction to explore the problem of the crossing numbers of two categories of join graphs that a special five-order graph with n isolated vertices as well as a star graph with circle in order to enrich the research results of the crossing numbers.The main work and innovation of this paper are as followsIn chapter two,the crossing number of a unconnected fifth order graph with n isolated vertices is determined,in which the fifth-order unconnected graph is composed of a complete tripartite graph K1,1,2 and a isolated vertice.In chapter three,we determine the crossing number of a star graph S6 with circle Cn.