Special Graph G With Path,Cycle And Acnode Of Join Crossing Number

The research on crossing numbers of graphs is originated in World War Ⅱ, when Pual Turan encountered a practical problem in a brick factory. It gradually developed into a very active branch of the disciplines of graph theory, attracting a large number of scholars'attention domestic and overseas. Besides, its theory has a wide range of applications in circuit board design, sketch recog-nition and redraw, and the graphic representations of the biological DNA, etc. However, to determine the crossing numbers of general classes of graphs have proven to be a NP-complete problem. Therefore, achievements on the crossing numbers of graphs are very few so far, and most of the graphs which crossing numbers are identified are special classes of graphs, therefore a lot of methods cannot be applied to the general classes of graphs, and what's more, sometimes it is very difficult to find a proper upper or lower boundary of the crossing num-bers of graphs. By using inductive method and reduction-to-absurdity method, this paper determines the crossing numbers of two special classes of graphs:The crossing number of join the special of H with six vertices path and cycle,and not connected graph of G with four vertices path and cycle.This paper consists of five parts:The first chapter mainly introduces the origin of the crossing numbers, theoretical and practical significance of researches on the crossing numbers of graphs, and current status of researches on it. Moreover, the main structure of this paper is briefly described.The second chapter discusses some basic concepts and important achieve-ments of the crossing numbers, which are required in reading this thesis.The third chapter illustrates the crossing number of join the special of H with six vertices path and upper or lower boundary of cycle.The fourth chapter introduces the crossing numbers of not connected graph of G with four vertices path and cycle.The last chapter is the conclusion part.