Augmented k-ary n-cubes

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, 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 k3+k-13, when n = 2; and has diameter at most k4(n+1), for n ⩾ 3 and k   even, and at most k4(n+1)+n4, for n ⩾ 3 and k odd.