On the k-ary hypercube tree and its average distance

The d-dimensional k-ary hypercube tree T(k)(d) is a generalization of the hypercube tree, also known in the literature as the spanning binomial tree. We present some of its structural properties and investigate in detail its average distance. For instance, it is shown that the binary hypercube tree has the anomaly of having two nodes in its centre as opposed to having one in hypercube trees of arity k > 2. However, in all dimensions, the centre, centroid and median coincide. We show that its total distance is sigma(T(k)(d)) = 2 sigma(H(k)(d)) -(2/k) (k(2)(d)) = dk(2d) -(d + 1)k(2d-1) + k(d-1), which is minimum. Consequently, for d >= 2, its average distance is mu(T(k)(d)) = (2d(k-1) k(d-1))/(kd-1) -2/k, whose limiting value is 2. This answers a generalization of a conjecture of Dobrynin et al. [Wiener index of trees: Theory and applications, Acta Appl. Math. 66 (2001), pp. 211-249] for the binary hypercube by the affirmative.