Crossing Number Of Issues On The Plot Map And Associated Map

Determining the crossing numbers of graphs has been proved to be NP-complete. The crossing numbers of very few families of graphs are know so far, and most of these graphs are Cartesian Products of special graphs, such as Cartesian Products of paths, cycles or stars with "small"vertex graphs. Concerning the crossing numbersfor join of two Graphs, the exact values of crossing numbers for join of two paths, join of two cycles, and for join of path and cycle have been determined. on the basis, in this paper, we determine the crossing numbers of Cartesian products (K_3,3-e)×P_n and G₂×S_n for a 6-vertex graph G₂,respectively:cr[(K_3,3 - e)×P_n] = 4n-2;cr(G₂×S_n)=6[n/2][(n-1)/2]+2[n/2];and further more , we determine the crossing numbers of G₂∨P_n and G₂∨C_n,respectively:cr(G₂∨P_n) = 6[(n+1)/2][n/2]+2[(n+1)/2] + 1;cr(G₂∨C_n) = 6[n/2][(n-1)/2]+2[n/2]+3.