On The Crossing Numbers Of Cartesian Products Of 5-vertices Graphs With Stars

The crossing number of graphs is a very important concept in morden graph theory. Scince early in the 1950s, the Hungarian mathematician Paul Turan who suggest the actual problom, which named " Turan's brick factory problem " by Zarankiewicz, gradually being a very active field in the world. It attracts many graph theory expert to work.The research work in the crossing number of graph is not an important in theory, but also more pratical, e.g. the circuit playout problems in VLST and playout problems in electric design, etc.. In 1983,Garey and Johnson proved that in general determining the crossing number of graphs is NP-complete.There are a few exact results on the crossing numbers of graphs class because of its complexity.In many cases, even it is very difficult to find out good bounds of the crossing numbers of graphs.Now, many articles are focus on investigating the crossing numbers of some special graphs, for exemple,these include the complete graph K_n for small n,the complete bipartite graph K_m,n for small m and any n,the complete tripartite graph K_1,m,n,some Cartisian product graph etc. In this paper, we study the crossing numbers of Cartesian products of stars S_n with several 5-vertex graphs.In chapter one. we introduce the backgrounds of the crossing numbers of and its development around the world, the meanings of the research and the problems we will solve.In chapter two, we give some conceptions and properties, and introduce the required knowledges about crossing numbers when read this paper.In chapter three, we discuss the crossing numbers of graphs G₁₂×S_n,G ₁₅×S_n and G₁₈×S_n,which crossing numbers are following: 1. cr(G₁₂×S_n) =n(n-1),n≥1. 2.cr(G₁₅×S_n)=Z(5,n)+2n+[n/2],n≥1.3.cr(G₁₈×S_n)=Z(5, n) +2n+[n/2],n≥1.In chapter four, there are some questions when researching into this problem, and the direction I will go ahead.