Crossing Number Of Cyclic Graphs C (n; {1, K})

Crosssing number is an important concept measuring the non-planarity of graphs. Bhatt and Leighton showed the corssing number of a network(graph) is closely related to the minimum layout area required for the implementation of a VLSI circuit for that network. However, it is intractable to calculate the crossing number of an arbitrary graph. Garey and Johnson have showed crossing number is NP-Complete. There are only a few infinite families of graphs whose crossing numbers are known. The crossing numbers of the complete bipartite graph and the complete graph are open problems in topological graph theory.Recently, many mathematicians focus on some graphs with good properities, such as the generalized Petersen graph, CmxCn and the circulant graph. Exoo et al. showed the crossing number of P(n,2). Fiorini showed crossing numbers of some generalized Petersen graphs with small order. Sarazin proved that the crossing number of P(10,4) is four. Liu Tongyin and Liu Yanpei showed the crossing number of C(n;{l,2}). Hao Rongxia and Liu Yanpei showed a new bound for crossing numbers of C(n;{1,k}). Richter and Salazar showed the crossing number of P(n;3). Yang Yuansheng and Zhao Chengye showed crossing numbers of C(n;{1l,n/2}). Salazar showed tight bounds for crossing numbers of C(n;{1,k}) and P(n,k).Firstly, it is proved that the crossing number of C(n; {1,3}) isIt verifies the conjecture proposed by Richter, Salazar, Hao Rongxia and Liu Yanpei.Secondly, this paper focuses on the crossing number of C(n;(1,n/2-1)). The value of crossing numbers for even n and the upper bound for crossing numbers for odd n are showed. for even n>8.Finally, crossing numbers of C(mk;{1,k}) and P(mk,k) are studied in this paper. Some close upper bounds and some exact values are showed.cr(C(3k;{1,k}) = k for k>3;cr(C{4k;{1,k})<2k + 1 for k>;cr(C(mk;{1,k})) ,m>5.cr(P(3k,k)) = k for k>; cr(P(4k,k))<2k +1 for k>;cr(P(mk,k)),m>.