Research On The Crossing Numbers Of Mycielski Graphs And Optimal 1-planar Graphs

The crossing number of a graph is a vital concept, as a parameter, it is related with chromatic number, genus and non-planarity of a graph. It comes from the Pual Turan's trick factory problem during the World War II, and it becomes a very active branch in graph theory, many authors have been studied in this area. As it was proved that determining the crossing numbers of general graphs is NP-complete. Because of its difficulty, there are only some special graphs whose crossing numbers are known.In this thesis, we study the crossing numbers of Mycielski graph, prove a sufficient and necessary conditions of cr(M(G))=2, and obtain some new properties about Mycielski graph. Moreover, we study the crossing number of one kind of graphs-the opti-mal 1-planar graphs. There are four chapters in this thesis.In Chapter 1, we introduce the backgrounds and origins of the crossing number in theory and reality. Futhermore, we give its developments and recent situations around the world, and present the meanings of the research. Then we give definitions, notations and a brief summary of basic content of this thesis.In Chapter 2, we study the crossing numbers of Mycielski graphs. Several Mycielski graphs have been discussed and some properties are proved in the first part. And a su-fficient and necessary conditions of cr(M(G))=2 is proved in the second part.In Chapter 3, we study the crossing number of the optimal 1-planar graph and obtain the crossing number of the optimal 1-planar graph G(V,E), that is cr(G)=│V│-2.In the last chapter, we make some conclusion of our research work and put forward some relative problems which we will go ahead.