The Crossing Numbers Of K_m×P_n And K_m,n×P_l

In 1983, Garey and Johnson have proved that the problem of determining the crossing number of an arbitrary graph is NP-complete. There are only a few infinite families of graphs whose crossing numbers are known today. The crossing numbers of the complete graph, the complete bipartite graph, the generalized Petersen graph, the Cartesian products and the circulant graph are main problems in the study of crossing number in recently years.In the research of the crossing number of Cartesian products, there are several known exact results on the crossing number of Cartesian products of paths, cycles or starts with "small" graphs. This paper focuses on the crossing number of the Cartesian products of path with complete graph K_m×P_n and the Cartesian products of path with complete bipartite graph K_m,n×xP_l. First, the upper bounds of the crossing numbers of these graphs are determined:At the same time, it is confirmed that the lower bound of the crossing number of K_mè­–_n is as follows:Further more, the crossing numbers of K₆è­–_n and K₂,nè­–_l are determined:Finally, the conjectures are given that the upper bounds of the crossing numbers of the Cartesian products of path with complete graph K_mè­–_n and the Cartesian products of path with complete bipartite graph K_m,nè­–_l are the exact crossing numbers of these graphs.