The Bounds Of The Crossing Number Of Augmented Cubes

Graph theory is an important branch of discrete mathematics, which has achieved rapid development and has been widely used in various fields, including physics, chemistry, communications science, computer technology, bio-genetics in the last two hundred of years. Let G be a simple connected graph with vertex set V(G) and edge set E(G). The crossing number of Graph G, cr(G), which is a topological invariant of graphs and an important measure of non-planar graphs, is the minimum number of pairwise intersections of edges in a drawing of G in the plane.Based on the theoretical and practical needs, people do a lot of research on the crossing number problem.Computing the crossing number was proved to be NP-complete by Garey and Johnson in1983 and could give impetus to the research of general NP-comlete problem. There are only a few infinite families of graphs for which the exact crossing numbers are known. The hypercube and its variants are of the most popular interconnection network because of its attractive properties, such as strong connectivity, small diameter, symmetry, recursive construction, relatively small degree, and regularity. The n-dimensional augmented cube AQn proposed by S.A. Choudum and V. Sunithain 2002 is one of these variations. It is not only retains some favorable properties of Qn but also possesses some embedding properties that Qn does not. Thus, it has drawn a great deal of attention of research.In section 3 of this paper, we do much in-depth research on the crossing number of graphs and design an algorithm CCN with branch and bound, backtracking method. With CCN, we could get good drawings of AQn graphs. Then we do analysis on the drawings, summarize their recursive law and at last we give the upper bound of cr(AQn): In section 4, we construct an arbitrary bijection of vertices of complete graph 2K,n onto AQn, combine with mathematical construction method and the analysis of congestion, we derive the lower bound of cr(AQn):Also, we make a study of the crossing number of AQn for n=7 in section 5 and we show good drawings of AQn for n=4,5,6,7.