Augmented cubes
Following the recursive definition of the hypercube Q(n), we define the augmented cube AQ(n). 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. (C) 2002 Wiley Periodicals, Inc.
hypercube diameter routing broadcasting simple graph distance connectivity embedding