The Lower Bound Of The Crossing Number Of K_1,1,m,n And K_1,3,3,n

The crossing number of graphs is a very important branch of graph theory.Over the years,many domestic and foreign scholars have engaged in the study of the problem of the crossing number of graphs.In fact,Garey and Johnson proved that determining the crossing number of a graph is a NP-complete problem.Due to the difficulty of the crossing number problem,the domestic and international research progress on this issue is very slow.So far,the crossing numbers of few complete multipartite graphs are known.This paper mainly studies the crossing number of several complete multipartite graphs.The main contents of this paper are as follows:(1)For the complete 4-partite graph K1,1,m,n,firstly,in order to get an upper bound of the crossing number of K1,1,m,n,we construct a good drawing of K1,1,m,n,Secondly,in order to get a lower bound of the crossing number of K1,1,m,n,by making appropriate adjustments on a good drawing of K1,1,m,n,we constitute a good drawing of complete tripartite graph K1,m+1,n+1.Finally,assuming that the crossing number of complete tripartite graph K2,m,n is z(m+2,n+2)-mn,we get the crossing number of K1,1,m,n when m and n are both odd:cr(K1,1,m,n)= z(m + 2,n)+[m/2]+[m-1/2]n+[m/2][n/2],and a conjecture of the crossing number of K1,1,m,n when m and n are other cases.(2)According to the local features of good drawings of complete 4-partite graph K1,2,2,n,we divide good drawings of K1,2,2,n into two categories.For the crossing number of K1,2,2,n:cr(K1,2,2,n)= z(5,n)+[3n/2].we prove it by a method similar to(1)but different from Ho.(3)For the complete 4-partite graph K1,3,3,n,firstly,we conjecture the crossing number of complete tripartite graph K3,4,n:cr(K3,4,n)= z(7,n)+ 4n + 2[n/2]+ 2.Secondly,in order to get an upper bound of the crossing number of K1,3,3,n,we construct a good drawing of K1,3,3,n.According to the local features of good drawings of K1,3,3,n,we divide good drawings of K1,3,3,n into three categories.In order to get a lower bound of the crossing number of K1,3,3,n,by making appropriate adjustments on a good drawing of K1,3,3,n,we constitute a good drawi-ng of complete tripartite graph K3,4,n+1.Finally,combining the conjecture of the crossing number of K3,4,n,we get a conjecture of the crossing number of K1,3,3,n:cr(K1,3,3,n)= z(7,n)+ 5n + 3[n/2]+ 3.