The Crossing Numbers And Related Characters Of Some Kinds Of Graphs

It is an important part for studying the characters of graphs in graph theory. This thesis is mainly on how to determine the crossing number of a graph when drawing which on the plane. Furthermore, the genus distributions of embedding circular graphs C(2m, m) on orientable surfaces are discussed.For some graphs, some edges of which must be crossed whatever they are drawn on the plane. The crossing number of a graph G , denoted by cr(G) , is the minimal number of pairwise intersections of edges in all the drawings of G on the plane, where the drawings satisfy:(a) two nonadjacent edges cross at most once,(b) no edge crosses itself,(c) adjacent edges never cross,(d) no more than two edges cross at a point of the plane,(e) the arc in the plane corresponding to an edge of the graph contains no vertex of the graph.There are not only enormous significance for theoretics on researching the crossing numbers of graphs, but also enormous significance for application. For example, the design of VLSI's chip.A 2-cell embedding of a graph on a surface is drawing the graph on the surface such that the edges of the graph cross only at the common vertex of them and every region of which is homeomorphic to an open disk. Many problems are involved in the 2-cell embedding investigation, such as the maximal genus, the minimal genus, the average genus and genus distribution etc.In this thesis, there are three chapters:In the first chapter, some useful knowledge for the thesis is introduced.In the second chapter, the crossing numbers of two kinds of graphs are gotten based on the former results. cr(S₃+S_n) = n² -(?) and cr(W_n×P_m) = (m -1)(?)+(m + 1), n≥3, m≥1 will be proved.In the third chapter, edge-adding method will be used and the recurrence formula for genus distribution of C(2m, m) will be gotten.