On the k-ary hypercube tree and its average distance

Abstract

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 , which is minimum. Consequently, for d≥2, its average distance is μ(T _k (d))=(2d(k−1)k ^d−1)/(k ^d −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.

Keywords:

• hypercube tree
• spanning binomial tree
• average distance
• total distance
• Wiener index

2000 AMS Subject Classifications :

• 05C12
• 05C05
• 05C85
• 90B18
• 90B20

Acknowledgements

The author is grateful to KFUPM for their continual support. He would especially like to thank the anonymous reviewers for their many helpful comments, suggestions and corrections that significantly improved the presentation. Thanks to the editor for the post-comments.