Augmented k-ary n-cubes

Xiang, Y.; Stewart, I.A.

doi:10.1016/j.ins.2010.09.005

Augmented k-ary n-cubes

Xiang, Y.; Stewart, I.A.

Authors

Y. Xiang

Professor Iain Stewart i.a.stewart@durham.ac.uk
Professor

Abstract

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.

Citation

Xiang, Y., & Stewart, I. (2011). Augmented k-ary n-cubes. Information Sciences, 181(1), 239-256. https://doi.org/10.1016/j.ins.2010.09.005

Journal Article Type	Article
Publication Date	Jan 1, 2011
Deposit Date	Aug 25, 2009
Publicly Available Date	Oct 25, 2010
Journal	Information Sciences
Print ISSN	0020-0255
Publisher	Elsevier
Peer Reviewed	Peer Reviewed
Volume	181
Issue	1
Pages	239-256
DOI	https://doi.org/10.1016/j.ins.2010.09.005
Keywords	Interconnection networks. Parallel computing. k-ary n-cubes. Augmented cubes.
Publisher URL	http://www.dur.ac.uk/i.a.stewart/Papers/Augkaryncube.pdf