Research On The Crossing Numbers Of Join And Cartesian Product Graphs

The crossing number of a graph is an important concept in the development of modern graph theory,mainly focusing on how to draw the graph in a plane such that the crossing number is the least.Pure mathematical methods are common utilize in most studies.However,to determine the crossing numbers of graphs is proved to be an NP-complete problem.Therefore,the results of crossing number is relatively rare except for some special and simple graphs.Even in some cases,it is very difficult to find a well-defined boundary of the graph includes upper and lower boundaries.This paper employed combination method,the ideas of induction and proof by contradiction to determine the crossing numbers of join graphs which derived from six-order and five-order graphs with n isolated vertices,along with studying the crossing number of the Cartesian product of stars.This thesis consists of six chapters.In chapter one.We introduce the origins,backgrounds and research trends of the crossing number,and the structure of this paper.In chapter two.Some basic concepts and some lemma and properties which associated with the graph are presented.In chapter three.We provide the crossing number of six-order graph and a join graph with n isolated vertices and the Cartesian product of star graph Sn,respectively.In chapter four.The crossing numbers of a five-order graph and the Carte-sian product of star graph Sn are determined.In chapter five.The crossing numbers of a six-order disconnect graph and a join graph with n isolated vertices are given.In chapter six.Summarize our researches and look forward to the work in future.