TOPICS
Search

Wiener Index

DOWNLOAD Mathematica NotebookDownload Wolfram Notebook

The Wiener index W, denoted w (Wiener 1947) and also known as the "path number" or Wiener number (Plavšić et al. 1993), is a graph index defined for a graph on n nodes by

W=1/2sum_(i=1)^nsum_(j=1)^n(d)_(ij),
(1)

where (d)_(ij) is the graph distance matrix.

Unless otherwise stated, hydrogen atoms are usually ignored in the computation of such indices as organic chemists usually do when they write a benzene ring as a hexagon (Devillers and Balaban 1999, p. 25).

The Wiener index W(G) of a graph G with vertex count |G| is related to the average disorder number A(G) of the graph by

A(G)=(2W(G))/(|G|)
(2)

(Fried 2022).

The Wiener index of a graph Cartesian product of graphs G_1 and G_2 is given by

W(G_1 square G_2)=|G_1|^2W(G_2)+|G_2|^2W(G_1)
(3)

(Yeh and Gutman 1994, Fried 2022).

The Wiener index is not very discriminant. In fact, the paw graph and square graph on four nodes are already indistinguishable using the Wiener index (both have value 8). The numbers of non-Wiener-unique connected graphs on n=1, 2, ... nodes given by 0, 0, 0, 2, 16, 108, 847, 11110, 261072, ... (OEIS A193217).

Precomputed values for many graphs are implemented in the Wolfram Language as GraphData[g, "WienerIndex"].

The following table summarizes values of the Wiener index for various special classes of graphs.

graph classOEISW(G_1), W(G_2), ...
Andrásfai graphA2920181, 15, 44, 88, 147, 221, 310, 414, ...
antelope graph n×nA2920390, infty, infty, infty, infty, infty, infty, 11548, 16660, ...
antiprism graphA002411X, X, 18, 40, 75, 126, 196, 288, ...
Apollonian networkA2890226, 27, 204, 1941, 19572, 198567, ...
black bishop graph n×nA2920510, 1, 14, 42, 124, 251, 506, 852, 1432, 2165, ...
cocktail party graphA001105infty, 8, 18, 32, 50, 72, 98, 128, 162, ...
complete bipartite graph K_(n,n)A0005671, 1, 5, 73, 2069, 95401, 6487445, ...
complete tripartite graph K_(n,n,n)A0941591, 11, 1243, 490043, 463370491, ...
complete graph K_nA0002170, 1, 3, 6, 10, 15, 21, 28, 36, ...
2n-crossed prism graphA292022X, 48, 132, 288, 540, 912, 1428, ...
crown graph K_2 square K_n^_A033428X, X, 27, 48, 75, 108, 147, 192, 243, ...
cube-connected cycle graphA292028X, X, 888, 9472, 76336, 559584, 3594952, ...
cycle graph C_nA034828X, X, 3, 8, 15, 27, 42, 64, 90, ...
Fibonacci cube graphA2384191, 4, 16, 54, 176, 548, 1667, 4968,, ...
fiveleaper graph n×nA2920400, infty, infty, infty, infty, infty, infty, 6364, 9888, 15216, ...
folded cube graphA292029X, 1, 6, 40, 200, 1056, 4928, 23808, ...
gear graphA049598X, X, 36, 72, 120, 180, 252, 336, 432, ...
grid graph P_n square P_nA1439450, 8, 72, 320, 1000, 2520, 5488, 10752, ...
grid graph P_n square P_n square P_nA2920450, 48, 972, 7680, 37500, 136080, 403368, ...
halved cube graphA2920440, 1, 6, 32, 160, 768, 3584, 16384, ...
Hanoi graphA2900043, 72, 1419, 26580, 487839, 8867088, ...
hypercube graph Q_nA0026971, 8, 48, 256, 1280, 6144, 28672, ...
Keller graphA292056infty, 200, 2944, 43392, 650240, 9889792, ...
king graph n×nA2920530, 6, 52, 228, 708, 1778, 3864, 7560, ...
knight graph n×nA2920540, infty, infty, 288, 708, 1580, 3144, 5804, 9996, ...
Menger sponge graphA292036612, 794976, 954380016, ...
Möbius ladderA180857X, X, 21, 44, 85, 138, 217, 312, 441, ...
Mycielski graphA2920550, 1, 15, 90, 435, 1926, 8175, 33930, ...
odd graph O_nA1363280, 3, 75, 1435, 25515, 436821, ...
pan graphA1808618, 16, 26, 42, 61, 88, 119, 160, 206, 264, ...
path graph P_nA0002920, 1, 4, 10, 20, 35, 56, 84, 120, ...
permutation star graph PS_nA2840390, 1, 27, 744, 26520, 1239840, ...
prism graph Y_nA138179X, X, 21, 48, 85, 144, 217, 320, 441, ...
queen graph n×nA2920570, 6, 44, 164, 440, 970, 1876, 3304, 5424, ...
rook graph K_n square K_nA085537X, 8, 54, 192, 500, 1080, 2058, 3584, 5832, ...
rook complement graph K_n square K_n^_A2920580, infty, 54, 168, 400, 810, 1470, 2464, ...
Sierpiński carpet graphA29202564, 13224, 2535136, 485339728, ...
Sierpiński gasket graphA2901293, 21, 246, 3765, 64032, 1130463, 20215254, ...
Sierpiński tetrahedron graphA2920266, 66, 1476, 42984, 1343568, 42744480, ...
star graph S_nA0002900, 1, 4, 9, 16, 25, 36, 49, 64, ...
sun graphA180863X, X, 21, 44, 75, 114, 161, 216, 279, 350, ...
sunlet graph C_n circledot K_1A180574X, X, 27, 60, 105, 174, 259, 376, 513, 690, ...
tetrahedral Johnson graphA292061X, X, X, X, X, 300, 1050, 2940, 7056, 15120, ...
torus grid graph C_n square C_nA12265754, 256, 750, 1944, 4116, 8192, 14580, 25000, ...
transposition graphA2920620, 1, 21, 552, 19560, 920160, 55974240, ...
triangular graphA0060110, 3, 18, 60, 150, 315, 588, 1008, 1620, ...
triangular grid graphA1128513, 21, 81, 231, 546, 1134, 2142, 3762, 6237, ...
web graphA180576X, X, 69, 148, 255, 417, 616, 888, 1206, 1615, ...
wheel graph W_nA002378X, X, X, X, 12, 20, 30, 42, 56, 72, ...
white bishop graph n×nA292059X, 1, 8, 42, 104, 251, 464, 852, 1360, 2165, ...

Closed forms are summarized in the following table. The cycle graph was considered by Plavšić et al. (1993) and Babić et al. (2002) and the path graph by Plavšić et al. (1993).

Andrásfai graph1/2(3n-1)(5n-1)
antiprism graph1/2(n+1)n^2
cocktail party graph K_(n×2)2n^2
complete graph K_n1/2n(n-1)
crossed prism graph4n(n^2+2)
crown graph S_n^03n^2
cycle graph C_n, n>=3{1/8n^3 for n even; 1/8(n-1)n(n+1) for n odd
gear graph6n(n-1)
grid graph P_n square P_n1/3n^3(n-1)(n+1)
grid graph P_n square P_n square P_n1/2n^5(n-1)(n+1)
halved cube graph{0 for n=1; n·2^(2n-5) for n>=2
hypercube graph Q_nn·4^(n-1)
Möbius ladder1/4n[2n(n+2)-3-(-1)^n]
Mycielski graph M_n1/(144)(216-272^(3+n)-563^n+814^n)
path graph P_n1/6n(n^2-1)
rook graph K_n square K_nn^3(n-1)
star graph S_n(n-1)^2
sun graphn(4n-5)
sunlet graph C_n circledot K_11/4n[(-1)^n+2n(n+4)-5]
triangular graph1/4n(n-1)^2(n-2)
wheel graph W_n(n-2)(n-1)

See also

Average Disorder Number, Balaban Index, Graph Distance Matrix, Kirchhoff Index, Resistance Distance, Topological Index, Wiener Sum Index

Explore with Wolfram|Alpha

References

Babić, D.; Klein, D. J.; Lukovits, I.; Nikolić, S.; and Trinajstić, N. "Resistance-Distance Matrix: A Computational Algorithm and Its Applications." Int. J. Quant. Chem. 90, 166-176, 2002.Devillers, J. and Balaban, A. T. (Eds.). Topological Indices and Related Descriptors in QSAR and QSPR. Amsterdam, Netherlands: Gordon and Breach, pp. 26 and 108-109, 1999.Entringer, R. C.; Jackson, D. E.; and Snyder, D. "Distance in Graphs." Czech. Math. J. 26, 283-296, 1976.Fried, S. "The Disorder Number of a Graph." 7 Aug 2022. https://arxiv.org/abs/2208.03788/.Hosoya, H. "Topological Index. A Newly Proposed Quantity Characterizing the Topological Nature of Structural Isomers of Saturated Hydrocarbons." Bull. Chem. Soc. Japan 44, 2322-2239, 1971.Plavšić, D.; Nikolić, S.; Trinajstić, N.; and Mihalić, Z. "On the Harary Index for the Characterization of Chemical Graphs." J. Math. Chem. 12, 235-250, 1993.Sloane, N. J. A. Sequence OEIS A193217 in "The On-Line Encyclopedia of Integer Sequences."Wiener, H. J. "Structural Determination of Paraffin Boiling Points." J. Amer. Chem. Soc. 69, 17-20, 1947.Wiener, H. "Influence of Interatomic Forces on Paraffin Properties." J. Chem. Phys. 15, 766, 1947.Wiener, H. "Vapor Pressure-Temperature Relationships Among the Branched Paraffin Hydrocarbons." J. Phys. Chem. 52, 425-430, 1948.Wiener, H. "Relation of the Physical Properties of the Isomeric Alkanes to Molecular Structure. Surface Tension, Specific Dispersion, and Critical Solution Temperature in Aniline." J. Phys. Chem. 52, 1082-1089, 1948.Yeh, Y.-N. and Gutman, I. "On the Sum of All Distances in Composite Graphs." Disc. Math. 135, 359-365, 1994.Zerovnik, J. "Szeged Index of Symmetric Graphs." J. Chem. Inf. Comput. Sci. 39, 77-80, 1999.

Referenced on Wolfram|Alpha

Wiener Index

Cite this as:

Weisstein, Eric W. "Wiener Index." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/WienerIndex.html

Subject classifications