On The Lower Bound For The Crossing Numbers Of Two Special Graphs

The crossing number of the graph is an important parameter of the graph,which is the standard to measure the distance between a graph and the plane graph,and has a fairly extensive practical application.But M.R.Garey and D.S.Johnson has proved out the figure on the crossing number calculation problem is a NP-hard problem[2],and the crossing number has always been a frontier problem in topology graph theory.There is no relatively uniform way to calculate the crossing number intersections of a graph.therefore,the figure of the number of cross the results so far are not rich.This dissertation focuses on the lower bound of the crossing numbers of two special graphs.Part Ⅰ:The relationship between the complete Tripartite graphs K3,3,n and the complete bipartite graph K6,n+3 is constructed using the local construction new graph method and its lower bound value is obtained.Part 2:Using contraction surgery,the lower bound value of Cartesian product graph K2,6 × Sn is obtained.Divided into the following five chapters:Chapter 1:Introduction,it mainly introduces the historical research back-ground of graph theory and the research results of several special types of graphs that have emerged at present,and briefly summarizes the research con-tents.Chapter 2:It gives the basic concepts,related properties and lemmas of some graph theories involved in this paper,and introduces the main results of this paper.Chapter 3:First introduced the concepts and lemmas needed in this chap-ter,and proved the lower bound of K3,3,n.Chapter 4:Given the lemmas needed in this chapter,establishing a rela-tionship of crossing number for cartesian product graph and complete tripar-tite graph,the conjecture cr(K2,m × Sn)= cr(K2,m,n)+n[m/2][m-1/2](m≥5)is partly solved.Chapter 5:summarization and prospects.