Augmented k-ary n-cubes

作者：Xiang Yonghong; Stewart Iain A^*

来源：Information Sciences, 2011, 181(1): 239-256.

DOI：10.1016/j.ins.2010.09.005

• Interconnection networks
• Parallel computing
• k-ary n-cubes
• Augmented cubes

We define an interconnection network AQ(n,k) which we call the augmented k-ary n-cube by extending a k-ary n-cube in a manner analogous to the existing extension of an n-dimensional hypercube to an n-dimensional augmented cube. We prove that the augmented k-ary n-cube AQ(n,k) has a number of attractive properties (in the context of parallel computing). For example, we show that the augmented k-ary n-cube AQ(n,k): is a Cayley graph, and so is vertex-symmetric, but not edge-symmetric unless n = 2: has connectivity 4n - 2 and wide-diameter at most max[(n - 1)k (n - 2), k + 7]; has diameter [k/3] + [k-1/3], when n = 2: and has diameter at most k/4(n + 1), for n >= 3 and k even, and at most k/4 (n + 1) + n/4, for n >= 3 and k odd.

• 出版日期2011-1-1