Geodesic
On the average path length of complete $m$-ary trees
Journal of integer sequences, Tome 17 (2014) no. 6.

Voir la notice de l'article provenant de la source Electronic Library of Mathematics

Summary: 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.
Keywords: average path length, Wiener index, m-ary tree 
@article{JIS_2014__17_6_a7,
     author = {Nyblom, M.A.},
     title = {On the average path length of complete $m$-ary trees},
     journal = {Journal of integer sequences},
     publisher = {mathdoc},
     volume = {17},
     number = {6},
     year = {2014},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/JIS_2014__17_6_a7/}
}
TY  - JOUR
AU  - Nyblom, M.A.
TI  - On the average path length of complete $m$-ary trees
JO  - Journal of integer sequences
PY  - 2014
VL  - 17
IS  - 6
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/JIS_2014__17_6_a7/
LA  - en
ID  - JIS_2014__17_6_a7
ER  - 
%0 Journal Article
%A Nyblom, M.A.
%T On the average path length of complete $m$-ary trees
%J Journal of integer sequences
%D 2014
%V 17
%N 6
%I mathdoc
%U http://geodesic.mathdoc.fr/item/JIS_2014__17_6_a7/
%G en
%F JIS_2014__17_6_a7
Nyblom, M.A. On the average path length of complete $m$-ary trees. Journal of integer sequences, Tome 17 (2014) no. 6. http://geodesic.mathdoc.fr/item/JIS_2014__17_6_a7/