The Crossing Number Of M(?)bius Cubes

The crossing number is an important measure of non-planarity of a graph, with applications in discrete and computational geometry, VLSI circuit design, and in several other areas of mathematics and theoretical computer science. This problem is NP-hard. Only a part of crossing numbers of several graph families have been determined, such as generalized Petersen graphs, complete graphs, complete bigraphs, Cartesian graphs and so on. Because the researches on hypercube and its variants are very rare, it is a challenging problem to determine the crossing numbers of these graphs.The Mobius cube is a variant of the hypercube. It has the same number of nodes and edges, but has only about half of diameter, wide diameter, and fault-diameter as the hypercube with the same dimension. It has drawn a great deal of attention of research.This paper deals with the crossing numbers of Mobius cubes. It gives the upper and lower bounds with the methods of computer constructive proof combined with mathematical proof. First of All, the paper constructs a better drawing of MQn for n≤6 based on the CCN algorithm. And then a drawing of MQn for n≥7 is given by expanding the drawing according to some kind of rule. As a result, the upper bound for the crossing number of MQn is given.This paper also gives the lower bound of MQn using the method proposed by Leighton.