close
Image TOPICS
Image
Search

Mean Distance

DOWNLOAD Mathematica NotebookDownload Wolfram Notebook

The mean distance of a (connected) graph is the mean of the elements of its graph distance matrix.

For a graph on n vertices with graph transmission T(G) and Wiener index W(G), the mean distance d^_ is related to these quantities by

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

The average vertex transmission is therefore nd^_.

Closed forms for some classes of named graphs 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+2)^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)

See also

Connected Graph, Graph Distance, Graph Distance Matrix, Graph Transmission, Vertex Transmission, Wiener Index

Explore with Wolfram|Alpha

Cite this as:

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

Subject classifications