The Crossing Number Of Cartesian Product Graph And Some Join Graph

The crossing number of a graph is an important topological measure for graphs. Gareyand Johnson have already known that determing the crossing number of graphs isNP-complete（see[1]）. There are a few exact results on the crossing numbers of graphs for itscomplexity.And there are only some special and simple graphs whose crossing numbers areknown. Even in many cases, it is very different to find the upper or lower bounds of thecrossing numbers of graphs. By using inductive method and reduction-to-absurditymethod,we determines the crossing numbers of the Cartesian products of pathsP_n with two7-vertex graphs. And we get the crossing numbers of the Join Graph of7-vertex graph Hand PathsP_n if the Zarankiewicz’s conjecture is hold for m=7, m≤n.Except that weget the crossing numbers of the Cartesian products of tree T with complete graphK₅.Thepaper is consist of6chapters:In chapter one, we introduce the origins and backgrounds of the crossing numbers,itstheorical and practical meanings, and its development around the world.In chapter two, we give some conceptions and properties, and introduce the requiredknowledges for reading this paper.In chapter three,we determine the crossing numbers of the Cartesian products of pathsP_nwith some graph of7-vertex is5n-1.And we determine the crossing numbers of theCartesian products of pathsP_n with some graph of7-vertex is6n.In chapter four, we get the crossing numbers of the Join Graph of7-vertex graph Hand PathsP_n if the Zarankiewicz’s conjecture is hold for m=7, m≤n.In chapter five, we get the crossing numbers of the Cartesian products of treeT withcomplete graphK₅.In chapter six, we make conclusions of this paper and put forward some relative problemswhich we will go ahead.