Augmented Cubes

Following the recursive definition of the hypercube Qn, we define the augmented cube AQn. After showing that its graph is vertex-symmetric, (2n - 1)-regular, and (2n - 1)-connected and that it has diameter [ n/2 ], we describe optimal routing and broadcasting procedures. The augmented cube possesses several embeddable properties that the hypercube and its variations do not possess. © 2002 Wiley Periodicals, Inc.