The Crossing Number Of Locally Twisted Cubes

The crossing number of a graph G is the minimum number of pairwise intersections of edges in all the drawing of of graph G, it's also a concept measure of non-planar graph and important measure parameters. Crossing number of graphs has very wide applications in the real life, for example, computer auto design, electronic components and wiring design in the Board, Internet network architecture design, etc. Therefore, it has been proposed and researched extensively by scientists.Crossing number of graphs is a topology constant of itself, Calculating the crossing number of a given graph is very difficult, it was proved to be NP-complete by Garey and Johnson. So, a very few families of graphs are determined exact crossing numbers, such as the generalized Petersen graph P(n,3), the Flower Snark graph Fn(n>3)and the Twisted Flower Snark graph Fn (n>3),etc. These conclusions strongly depend on their structures and their small degree. Most of the other graphs, such as the complete bipartite graph, the complete graph and the circulated graph,etc. are only given the crossing boundaries, so it's still active and to be resolved problem.The locally twisted cubes-LTQn is a variants of Qn, and there has good properties, such as smaller diameter, and has more important applicatios in Internetconnection network structure. In this paper, we deeply studied the locally twisted cube, in the help of computer and a large number of drawing experiments, for n (n≥6), we give a good general drawing and with the dimensions increase, how to draw from n-dimensional to extended n+1 dimensional. Based above, we give the best upper bound of locally twisted cube (LTQn) crossing number:For the n-dimensional LTQn, we proved that any two vertices of LTQn, there exists a unique dimension-ordered path P joining the two vertices,and any edge xy,and there are 2" different dimension-orderedpaths containing xy,so we get it's congestion.By constructing a embedding of known crossing number of graph and LTQn, we get the lower bound of crossing number of locally twisted cube: Therefore, we concluded the upper and lower bounds of the crossing number of locally twisted cube:...