We use cookies to ensure that we give you the best experience on our website. By continuing to browse this repository, you give consent for essential cookies to be used. You can read more about our Privacy and Cookie Policy.

Durham Research Online
You are in:

Augmented k-ary n-cubes.

Xiang, Y. and Stewart, I. A. (2011) 'Augmented k-ary n-cubes.', Information sciences., 181 (1). pp. 239-256.


We define an interconnection network AQn,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 AQn,k has a number of attractive properties (in the context of parallel computing). For example, we show that the augmented k-ary n-cube AQn,k: is a Cayley graph (and so is vertex-symmetric); has connectivity 4n-2, and is such that we can build a set of 4n-2 mutually disjoint paths joining any two distinct vertices so that the path of maximal length has length 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(n+1)/4, for n ≥ 3 and k even, and at most k(n+1)/4+n/4, for n ≥ 3 and k odd.

Item Type:Article
Keywords:Interconnection networks. Parallel computing. k-ary n-cubes. Augmented cubes.
Full text:(AM) Accepted Manuscript
Download PDF
Publisher Web site:
Date accepted:No date available
Date deposited:25 October 2010
Date of first online publication:January 2011
Date first made open access:No date available

Save or Share this output

Look up in GoogleScholar