| The crossing number of graphs is an important topological invariant of graphs,which refers to the smallest number of crossings among all plane drawings of graph.By the parameter of crossing number,we can describe the geometric features of graphs more vividly,but there is no consistent method to determine the crossing number of graphs.M.R.Garey and D.S.Jonson have proved that determining the crossing number of graphs is a NP-complete problem,which is really not easy to study.The research of domestic and foreign scholars in this direction is also mainly aimed at graphs with special structure,they study the crossing number of the join graphs and the cartesian products of small orders graphs with path、cycle、star.This paper mainly uses proof by contradiction、exclusive method、combination counting etc to study the crossing number of the join graph S7+Cn and S8+Cn(Sn is a star,Cn is a cycle).In addition,the crossing number of the cartesian product of the special 6-vertex graph H and the star Sn、the join graph of H and Pn is given.In the first chapter,the background of graph crossing number is briefly explained,and its significance in various fields and the current research situation are analyzed,the basic knowledge related to the crossing number of graphs is then stated.In the second chapter,we determine the crossing number of the join graph S7+Cn and S8+Cn.In the third chapter,we determine the crossing number of the cartesian product H × Sn and the join graph H+Pn.The last chapter is a summary of the paper and the prospect of future research direction. |
