On The Crossing Number Of A Graph

The problem of crossing numbers of graphs originated in a practical appli-cation, whose theory has been widely applied in many fields, such as the design of electronic circuits, and the identification and repaint of sketch, and the graph-ical representation of DNA in biology engineering and so on. Many scholars at home and abroad have engaged in the investigation on crossing numbers of graphs. However, it has been proven that computing the crossing number of a graph is NP-complete. Because of its difficulty, the results of crossing numbers of graphs are only very scarce up to date. Generally, the classes of graphs whose crossing numbers can be determined have special structures, it makes that lots of methods can't be generalized. In some cases, it is very difficult to find the upper or lower bounds for the crossing number of graphs. In this paper, we study the crossing numbers of products of graphs, as well as joins of graphs, etc, with some new methods. The crossing numbers of some products of graphs and joins of graphs are determined, and some properties of crossing numbers of graphs are obtained in this paper. As follows.(1) A property of zip products is obtained. As application of the property, we prove that for any graph G with four dominating vertices, it has(2) With "adding an edge in the local", we determine the crossing numbers of Km\e, m≤12. Furthermore, the crossing numbers of Km×Pn, m≤10, are determined, which is consistent with Zheng and Yang's conjecture for the crossing numbers of Km×Pn.(3) Klesc has determined the crossing numbers of K4\e×Pn and K5\e×Pn. And, Yang et al. have determined the crossing numbers of K6\e×Pn. With different methods, we determine the crossing numbers of K7\e×Pn and K9\e×Pn.(4) Modifying Klesc's commonly used contraction operation, we show that cr(K3,3×Sn)= cr(K3,3,n)+3n and cr(K2,2,2×Sn)= Z(6, n)+6n. (5) Using the structural characteristics of K2.3\e, the crossing numbers of join of K2,3 with path and cycle are obtained. Our proof is simple.(6) The crossing numbers of joins of K3,3 - 2K2 with paths and cycles, as well as products of K3,3—2K2 with stars are determined. Although, using the method of "edge set partitioning", thanks to flexible use of the structural characteristics for 6-cycle, there is no need to list all the drawings of K3,3—2K2.(7) With combinatorial counting method, we give two recursive inequalities for crossing numbers of graphs. As application of the two inequalities, we obtain the crossing number of K4,n\e, and give a simple method of determining the crossing number of K1,3,n.In addition to the above contents, this thesis also provides a thorough sur-vey of results known for the crossing numbers of graphs. The survey especially focuses on products of graphs.