Studies On The Crossing Numbers Of Some Typical Graphs And Related Problems

The crossing number pf a graph is a classical topological invariant of the graph,figure ground says,it is an important parameter to measure how far a graph is from the plane graph.The problem for crossing number of a graph arises from a practical puzzle that the Hungarian mathematician Turan excoun-tered in a brick factory.Then,the concept of crossing number of a graph was proposed.Subsequently,scholars initiated the extensive studies on this param-eter,and made it an active research field in graph theory.The study of this problem not only has profound theoretical significance,but also extensive prac-tical application value.The investigation on the crossing number of a graph is a classical but very difficult problem.In fact,it has been proven that comput-ing the crossing number of a given graph is NP-complete.There is no uniform approach for studying the crossing number of a graph,and for two graphs with very similar structure,the approach may be completely different.Thus,the results of the crossing numbers of graphs are very few.In this paper,some new methods are used to study the crossing numbers of some specific graphs.The conclusions are as follows:In chapter 2,we get some relationships between rotation and crossing num-ber,furthermore,using these results,we determine the crossing number of join of a disconnected graph on five vertices with n isolated vertices,where the disconnected graph made up of one complete graph K4 and an isolated vertex.In chapter 3,we first obtain the crossing number of join of the wheel graph W5 with n isolated vertices,by applying the method "local vertex's degree modified".Afterwards,combining with some properties of zip products,we give the crossing numbers of cartesian product of Wm,m=3,4,5,with any tree T.The result complements a recent result by Klesc,who established the crossing number of wheel with a tree of maximum degree at most five.In chapter 4,using a new method,we determine the crossing number of K5,n\e,where n is a non-negative integer.The result confirms a conjecture that Chia et al.made in 2005.In addition,in chapter 1,we elaborate the concepts and terms involved in this article,and the current research status of crossing number problem.