The Crossing Number Of Bubble-Sort Graph B_n And The Generalized Petersen Graph P(10,3)

The crossing number of a graph G (denoted by cr(G)) is an important topological invariant of graph and an important scale to measure the graph nonplanarity. It turns out that the crossing number problem has played an important role not only in graph theory, but also in the design of VLSI circuits and computer-aided design and drafting. However, because computing the crossing number of a specific graph has been proved to be a NP-complete problem, it is not surprising that the crossing numbers of only a few graph families are exactly known, such as the Cartesian products of paths, cycles and small graphs; for some special graphs, such as complete graphs and complete bipartite graphs, there are only some conjectures about their crossing numbers.The n-dimensional bubble-sort graph Bn is a new kind of network topology, which is structured with the Cayley method. Compared with the n-dimensional hypercube Qn, Bn has better performance, as measured by connectivity and fault tolerance, which results in the attention and studying of researchers from different areas. However, there is not much studying about its crossing number, since the quantity of its vertices increases as the factorial of its dimension. In this paper, we give a kind of recursive drawing for Bn on the base of results from computer calculation and mathematical analysis. Moreover, for n<7, we give some good drawings for Bn; for n>7, we study the categories of the crossings in the recursive drawing, and by estimating the quantity of the crossings in the drawing, we give an upper bound for cr(Bn), that isAs one of the research focuses in this field, the crossing number of the generalized Petersen graph always holds researchers’attention, resulting in many relative studyings. For instance, as a classical problem, the crossing number of the generalized Petersen graph P(3k+1,3) has been proved by foreign researchers by induction. However, as the base case of their proof, the crossing number of P(10,3) has no mathematical proofs, but only the computer verification. And the only theoretical result on its crossing number is cr(P(10,3))>5. In this paper, we study the drawing of P(10,3) and the feature of the drawings of its subgraphs, and in this way we prove cr(P(10,3))=6.