The Crossing Number Of Double Generalized Petersen Graph DP(2k+1,1)

The crossing number of graphs plays an important role in graph theory,This important parameter measures how far a graph differs from its plane embedding.Many scholars have actively engaged in the research of this field at home and abroad,and have obtained many essential and wonderful results in the last hundred years.A number of scholars have proved that determining the crossing number of a graph is a NP-complete problem.At present,most of the research focuses on the graph class with special structure,and it is very difficult to prove the crossing number of graphs because many methods cannot be extended to the general graph class.In this thesis,the lower bound of crossing number of double generalized Petersen graph DP(7,1)is proved by contradiction.The problem of the crossing number of generalized Petersen graph has always attracted much attention.For the crossing number of generalized Petersen graph P(n,k),Lin Xiaohui and other scholars proposed the conjecture of the crossing number of generalized Petersen graphs P(4k+2,2k): that is k ≥3,the crossing number of generalized Petersen graph P(4k+2,2k)is 2k+1 holds.And they used a computer program to get the crossing number of graph P(14,6)is 7,We gave a mathematical proof of this result.By giving a good drawings of the generalized Petersen graph P(4k+2,2k),the crossing number of graph P(4k+2,2k)is determined to be at most 7.