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

## 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.

Item Type: | Article |
---|---|

Keywords: | Interconnection networks. Parallel computing. k-ary n-cubes. Augmented cubes. |

Full text: | (AM) Accepted Manuscript Download PDF (269Kb) |

Status: | Peer-reviewed |

Publisher Web site: | http://dx.doi.org/10.1016/j.ins.2010.09.005 |

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

Export: | |

Look up in GoogleScholar |