close
Image TOPICS
Image
Search

Mean Distance

DOWNLOAD Mathematica NotebookDownload Wolfram Notebook

The mean distance of a (connected) graph is used with two closely related normalizations. The first averages all entries of the graph distance matrix, including the diagonal entries d(v,v)=0; Garijo et al. (2023) denote this normalization by mu_d(G) and note that it is the arithmetic mean of the entries of the distance matrix. The second, used for example by Doyle and Graver (1977) and described by Garijo et al. (2023) as the "most usual" convention, averages the nonzero distances over unordered pairs of distinct vertices.

The convention used here and by the GraphData property "MeanDistance" is the all-distance-matrix-entry normalization. For a graph on n vertices with graph transmission T(G) and Wiener index W(G), it is given by

d^_=(2T(G))/(n^2)
(1)
Image=(2W(G))/(n^2).
(2)

Closed forms for some classes of named graphs under the all-distance-matrix-entry convention are given in the following table.

classmean distance
Andrásfai graph(5n-4)/(3n-1)
antiprism graph1/4(n+1)
complete bipartite graph K_(m,n)(2[m^2+n^2+mn-(m+n)])/((m+n)^2)
complete bipartite graph K_(n,n)(3n-2)/(2n)
complete tripartite graph K_(n,n,n)(2(2n-1))/(3n)
complete tripartite graph K_(k,m,n)(2(k^2+m^2+n^2-k-m-n+km+kn+mn))/((k+m+n)^2)
complete graph K_n(n-1)/n
cycle graph C_n(2n^2+(-1)^n-1)/(8m)
empty graph K^__n{0 for n=1; infty otherwise
grid graph P_m square P_n((m+n)(mn-1))/(3mn)
grid graph P_n square P_n(2(n^2-1))/(3n)
grid graph P_n square P_n square P_n((n-1)(n+1))/n
hypercube graph Q_n1/2n
Möbius ladder(2n^2+4n-(-1)^n-3)/(8n)
path graph P_n((n-1)(n+1))/(3n)
prism graph Y_n(2n^2-4n+(-1)^n-17)/(8(n+2))
star graph S_n(2(n-1)^2)/(n^2)
wheel graph W_n(2(n-2)(n-1))/(n^2)

Under the distinct-vertex-pair convention, the mean distance is instead

mu(G)=1/((n; 2))sum_({u,v} subset= V(G))d(u,v)
(3)
Image=n/(n-1)d^_
(4)
Image=(2W(G))/(n(n-1))
(5)

for connected graphs with n>1.

See also

Connected Graph, Graph Distance, Graph Distance Matrix, Graph Transmission, Transmission-Minimal Regular Graph, Vertex Transmission, Wiener Index

Explore with Wolfram|Alpha

References

Doyle, J. K. and Graver, J. E. "Mean Distance in a Graph." Disc. Math. 17, 147-154, 1977.Garijo, D.; Márquez, A.; and Silveira, R. I. "Continuous Mean Distance of a Weighted Graph." Results Math. 78, 139, 2023. https://doi.org/10.1007/s00025-023-01902-w.

Referenced on Wolfram|Alpha

Mean Distance

Cite this as:

Weisstein, Eric W. "Mean Distance." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/MeanDistance.html

Subject classifications