Augmented cubes

Abstract

Abstract Following the recursive definition of the hypercube Q n , we define the augmented cube AQ n . After showing that its graph is vertex‐symmetric, (2 n − 1)‐regular, and (2 n − 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.