An upper bound for the crossing number of augmented cubes

Abstract

A good drawing of a graph G is a drawing where the edges are non-self-intersecting and each of the two edges have at most one point in common, which is either a common end vertex or a crossing. The crossing number of a graph G is the minimum number of pairwise intersections of edges in a good drawing of G in the plane. The n-dimensional augmented cube AQ _n , proposed by S.A. Choudum and V. Sunitha [Augmented cubes, Networks 40 (2002), pp. 71–84], is an important interconnection network with good topological properties and applications. In this paper, we obtain an upper bound on the crossing number of AQ _n less than .

Keywords:

• drawing
• crossing number
• augmented cube
• hypercube
• interconnection network

2010 AMS Subject Classifications: :

• 68R10
• 05C10

Acknowledgements

The authors are grateful to the referees for their valuable comments and suggestions. This research was supported by NSFC (11001035, 60973014, 60803034) and SRFDP (200801081017).