| The crossing number is an important concept measuring the non-planarity of graphs. Garey and Johnson have proved that the problem of determining the crossing number of an arbitrary graph is NP-complete. The crossing numbers of very few families of graphs are known exactly. Many researchers focus on the crossing numbers of the complete graph, the complete bipartite graph, the generalized Petersen graph, the circulated graph and Cartesian product of small graphs with paths stars or cycles.Kn(o|¨)del graph is a kind of networks. It is helpful for understanding the topological characters of the networks to study their crossing numbers. This paper focus on the crossing numbers of Kn(o|¨)del graph W3,n firstly, even n ≥ 8. It gives good drawings of W3,n and the crossing numbers upper bounds of W3,n· Different grouping methods and different crossing calculating functions are designed to determine the crossing numbers lower bounds of W3,n· The crossing numbers of W3,n are:Ringeisen and Beineke give the crossing numbers of K3□Cn and K4□Cn. This paper also study the crossing numbers of Cartesian product of the complete graph with cycle Km□Cn. Different grouping and crossing crossing calculating methods are designed to determine the crossing numbers lower bounds of Km□Cn:The good drawings of Km□Cn are constructed by modifying the bounding conditions of crossing numbers calculating algorithm CCN, and the upper bounds of the crossing number of Km□Cn are certained:Since when m ≤ 12, Guy's conjecture about the crossing number of the complete graph is true, when m ≤ 10 and even n, we have:... |
