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 Km×Pn and the Cartesian products of path with complete bipartite graph Km,n×xPl. 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 Km譖n is as follows:Further more, the crossing numbers of K6譖n and K2,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 Km譖n and the Cartesian products of path with complete bipartite graph Km,n譖l are the exact crossing numbers of these graphs. |