The Crossing Number Of A Class Of Infinite Graphs

The crossing number of graphs is an important part of graph theory.In the past 100 years,many scholars at home and abroad have studied the problem of the crossing number of graphs.In fact,some scholars have proved that determining the crossing number of a graph is a NP-complete problem.Due to the difficulty of proof,the research progress in the field of the crossing numbers at home and abroad is slow.So far,only few crossing numbers of several types of graphs can be proved.This paper mainly studies the crossing number of generalized Petersen graph P(12,5)and a class of infinite graphs.The crossing number of hexagonal graph H3,n has been proved.This paper studies the hexagonal graph H4,n.For the graph Hm,n,Wang Jing's paper gives the drawing and the conjecture of the crossing number.This paper proves that the conjecture of the crossing number is correct.Different edge grouping methods of the hexagonal graph H4,n and crossing calculating functions are designed to give its lower bound,which proves:Cr(H4,n)=2n(n?2).This paper gives the conjecture of the crossing number of the generalized Petersen graph P(2m+2,m)(m?5)that is cr(P(2m+2,m))?m+1(m?5).However,as the starting point of the induction method,the correlation result of the crossing number of P(12,5)is only a result verified by a computer,and there is no rigorous mathematical proof.In this paper,combined with the proof method of the generalized Petersen graph P(10,3),different edge grouping methods of the generalized Petersen graph P(12,5)are classified.Some lemmas are obtained by studying the properties of subgraphs of P(12,5),and then the lower bound of the crossing number of P(12,5)is at least 6.