##
**
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 *S*_{N}
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 *S*_{N},
from which a closed-form expression
for *S*_{N} is obtained.
Using this explicit expression for *S*_{N}, 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**