The Crossing Number Of Generalized Petersen Graph P(4k,4)

Graph theory is an important branch of discrete mathematics and the crossing number of graphs is also an important branch of graph theory.Many scholars at home and abroad have paid extensive attention to the problem of the crossing number of graphs.The concept of crossing number comes from Turán problem of the brick factory.In order to reduce the accidents on the transportation rail between the brick kiln and the warehouse,it is necessary to reduce the number of crossing points between the rails as much as possible.The mathematical model of this problem is to find the crossing number of the complete bipartite graph.Garey and Johnson proved that the problem of determining the number of intersects of graphs is NP-hard,so most of the current research results on the crossing number of graphs are focused on some specific graph classes,and only a few of the crossing numbers of graph classes have been confirmed,such as the Cartesian products of paths,cycles and small graphs;for some specialgraphs,such as complete graphs and complete bipartite graphs,there are only some conjecturesabout their crossing numbers.In this thesis,the crossing number of generalized Petersen graph P（4k,4）and complete 4-partite graph K_1,1,m,nare studied.In 1986,for the crossing number of the generalized Petersen graph P（4k,4）Fiorini once listed that the crossing number of the generalized Petersen graph P（（2n）k,2n）is less than or equal to kn（n-1）.However,Fiorini proved the crossing number of P（3k,3）by induction and then directly gave the crossing number of P（4k,4）as 2k,the proof that the crossing number of P（4k,4）is obtained from the crossing number of P（3k,3）is wrong.In 2008,Chimani using the algorithm in his doctoral thesis,obtained that the crossing number of P（4k+4,4）is 2k+2 when 3≤k≤43,and cr（P（8,4））=1 when k=1 and cr（P（12,4））=4 when k=2.From this,Chimani guesses that the crossing number of P（4k,4）is 2k for k≥4.In this thesis,the crossing number of generalized Petersen graph P（4k,4）are studied by mathematical induction and reduction.We mainly prove this conjecture.Firstly,a transitive decomposition of P（4k,4）is given.With the sufficient and necessary conditions for the lower bound of the crossing number of generalized periodic graphs,the lower bound of the crossing number of P（4k,4）is determined.In 1954,the well-known Zarankiewicz’s conjecture（ZC）asserted cr(K_m,n).In 1971,Harborth gave a conjecture（HC）oncr(K_x1,,xn).In 2021,Ho et al.verified that HC’s conjecture about K_1,m,n is correct when ZC is correct.In this thesis,a good drawing of K_m+1,n+3and a good drawing of K_m+3,n+1 of complete 4-partite graphs K_1,1,m,n can be obtained by local modification of any good drawing method of K_1,1,m,n,so as to prove the lower bound of the crossing numbers of K_1,1,m,n when m and n are both even.By the same method,two good drawings of complete tripartite graphs K_1,m+1,n+1can also be constructed,thus proving the lower bound of the crossing number of K_1,1,m,n when m and n are both even.And construct a good drawing of complete tripartite graphs_1,8+1,9)+1) and a good drawing of complete bipartite graphs₈+1,9)+2) and prove the lower bound of crossing number of K_1,1,m,n when m is even and n is odd.The lower bounds in our result imply that if both m and n are even and ZC is true,then HC on K_1,1,m,nholds;if at least one of m and n is odd and both ZC and HC on K_2,m,nare true,then HC on K_1,1,m,n holds.