The Crossing Number Of FQ_n And Q_n

The crossing number has promising future not only in the design of VLSI, but also in the filed of CAD. However, Garey and Johnson have proved that the problem of computing the crossing number of a graph is NP-complete in 1983. There are only few graphs whose accurate crossing numbers are known, such as the generalized Petersen graph, the Cartesian product of small graphs with five vertices and path.Hypercube and its variant are a kind of graph family with fine connecting features. And the study of the crossing number of them is significant to the field of crossing number. However for a long time, the only known result on the exact value of them has been cr(Q3)=0 and cr(Q4)=8. Hence, it is more practical to find the upper and lower bounds of the crossing number of hypercube and its variant.This paper focuses on the crossing number of FQn and confirms its upper and lower bound. With the help of computer, we construct a drawing of FQ3 with few crossing number. And then with the beginning drawing of FQ3, we prove the upper bound of the crossing number of FQn by recursive construct the drawing of it:At the same time, based on the theory of the graphic embedding, the paper studies the lower bound of the crossing number of FQn:Moreover, the paper determines the upper bound crossing number of Qn. In 2008, Sykora and Vrt'o proposed a kind of construction of Qn in the plane and proved the upper bound of the crossing number of it: This paper proposes another drawing of Qn, by the use of which we improve the upper bound of the crossing number of it:...