On the Average Path Length of Complete m-ary Trees
M. A. Nyblom
School of Mathematics and Geospatial Science
Melbourne, Victoria 3001
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,
Received January 23 2014;
revised version received May 7 2014.
Published in Journal of Integer Sequences, May 8 2014.
Journal of Integer Sequences home page