SUMMING THE SHORTEST PATH LENGTHS IN A RECTANGULAR LATTICE VIA RECURSION
Define the average path length in a connected graph G as the sum of the lengths of the shortest path between pairs of nodes is divided by the total number of pairs of nodes. Denoting the sum of the shortest path lengths between all pairs of nodes in an rectangular lattice, having fixed rows and variable rows by we derive a first order linear but non-homogeneous recurrence relation for from which a closed-form expression for is obtained. Using this explicit expression for one can then show that the average path length within this graph must be asymptotic to where D is the diameter, that is, the longest shortest path.
Wiener index, square lattice.