The shuffle-cubes and their generalization

Abstract

In this paper, we first present a new variation of hypercubes, denoted by SQ(n) .SQ(n) is obtained from Q(n) by changing some links. Sa, is also an n-regular n-connected graph but of diameter about n/4. Then, we present a generalization of Se,. For any positive integer g, we can construct an n-dimensional generalized shuffle-cube with 2(n) vertices which is n-regular and n-connected. However its diameter can be about n/g if we consider g as a constant. (C) 2001 Elsevier Science B.V. All rights reserved.