On The Crossing Numbers Of The Cartesian Products Of Circular Graph And Some Special Graphs With Paths,Stars,Trees And Cycles

The crossing number of graphs is a vital concept in morden graph theory, we have already known that to determine the crossing numbers of graphs is NP-complete. At present the classes of graphs whose crossing numbers have been de-termined are very scarce,and there are only some special graphs whose crossing numbers are known.In this paper,we study the crossing numbers of the Cartesian products of paths,stars,cycles with circular graphs,a Petersen graph and some special graphs,and we discuss the crossing numbers of one suspension and a double suspension of circular graph C(l,2),and explore the crossing numbers of the Cartesian products of outplanar graphs with cycles.At first,in Chapter one,we introduce the backgrouds and origins of the crossing number and its developments and recent situations around the world,and present the meanings of the research.In Chapter two,we give some conceptions and properties of the crossing number, and present the properties of n-connected graph and circular graphs and so on.In Chapter three,properties of K_2,2,2 and K_1,1,2,2 are investigated,and with the results of the crossing number of P(3,1) and K_2,4 with paths,the crossing numbers of Cartesian products of paths with K_1,1,2,2 and three speical 6-vertex graphs are determined.In Chapter four,applying the results of crossing numbers of K_1,3,n and K_2,3,n and the properties of n-connected graph,we obtain the crossing numbers of the Cartesian products of paths with circular graph C(7,2) and a 3-connected graph of seven vertices.In Chapter five,the properties of Petersen graph P(4,1) and the relations of P(4,1) and circlar graph C(8,2) being studied,the crossing number of Cartesian products of paths with C(8,2) and P(4,1) are determined.In Chapter six,by the properties and drawings of one suspension and a double suspension of circular graph C(l,2) which is 4-connected graph,we obtain the crossing numbers of one suspension and a double suspension of circular graph C(l,2).In Chapter seven,we improve on the methods of chapter's four and five,and determine the crossing numbers of Cartesian products of paths with circular graphs C(9,2),C(10,2) and C(12,2).In Chapter eight,supposing that the conjecture of Zarankiewicz is true,and letting there be no crossing points in the principle cyle of C(l,2),we determine the crossing numbers of Cartesian product of paths,stars,trees with C(l,2).In Chapter nine,letting there be no crossing points in the principle cyle of C(l,2),we study the lower bound on the crossing numbers of Cartesian products of cycles with C(l,2),and the crossing numbers of Cartesian products of cycles C_n with some outplanar graphs.In the last chapter,we make a summary of th paper and intruduce the directions of our research work and put forward some relative problems which we will go ahead.