The Crossing Number Of Chordal Ring Graphs CR_8k(1,3,9)

The crossing number of graphs is an important branch of graph theory.Many scholars at home and abroad have paid extensive attention to and studied the crossing number of graphs.Garey and Johnson proved that the problem of determining the number of intersects of graphs is NP-complete,so the problem of the number of intersects of graphs is still worth studying.However,due to the difficulty of exploration and proof,the research on the crossing number of graphs is slow at home and abroad.So far,the research results of graph crossing number focus on typical graph class,and only get the exact crossing numbers of very few families graphs.In this paper,the crossing number of chordal ring graphs CR8k(1,3,9)are studied by mathematical induction and reduction.The upper bound of Chordal Ring graph CR8k(1,3,9)is determined.By mathematical induction,on the basis of k=2,cr(CR16(1,3,9))=4,and assuming k-1,the inequality is valid for cr(CR8(k-1)(1,3,9))? 2(k-1).In this paper,the edge set of CR8k(1,3,9)is divided into 2k groups with no intersection by the method of inverse proof,all possible cases are discussed,and the lower bound of CR8k(1,3,9)of Chordal Ring graph is proved.It is thus proved that:cr(CR8k(1,3,9))=2k((k? 2).