Journal of Integer Sequences, Vol. 17 (2014), Article 14.6.3

On the Average Path Length of Complete m-ary Trees


M. A. Nyblom
School of Mathematics and Geospatial Science
RMIT University
Melbourne, Victoria 3001
Australia

Abstract:

Define the average path length in a connected graph as the sum of the length of the shortest path between all pairs of nodes, divided by the total number of pairs of nodes. Letting SN denote the sum of the shortest path lengths between all pairs of nodes in a complete m-ary tree of depth N, we derive a first-order linear but non-homogeneous recurrence relation for SN, from which a closed-form expression for SN is obtained. Using this explicit expression for SN, we show that the average path length within this graph/network is asymptotic to D - 4/(m - 1), where D is the diameter of the m-ary tree, that is, the longest shortest path. This asymptotic estimate for the average path length confirms a conjectured asymptotic estimate in the case of complete binary tree.


Full version:  pdf,    dvi,    ps,    latex    


Received January 23 2014; revised version received May 7 2014. Published in Journal of Integer Sequences, May 8 2014.


Return to Journal of Integer Sequences home page