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 topological index defined for a finite connected graph on n>=1 vertices by

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

where (d)_(ij) is an entry of the graph distance matrix. For a disconnected graph, the same sum gives W=infty when distances between different components are taken to be infinite.

For a connected graph, the Wiener index is therefore identical to the graph transmission T(G). Equivalently, if T(v_i) are the vertex transmissions of G, then

W(G)=1/2sum_(i)T(v_i).
(2)

It is related to the mean distance convention that averages all entries of the graph distance matrix by d^_=2W(G)/n^2, and to the common convention that averages over unordered pairs of distinct vertices by mu(G)=2W(G)/(n(n-1)) for n>=2.

The Xu index is similarly a logarithmic descriptor formed from the vertex transmissions, with each term weighted by the corresponding vertex degree.

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|).
(3)

(Fried 2022, pp. 14-15).

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).
(4)

(Yeh and Gutman 1994; Fried 2022, p. 14).

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 simple graphs on n=1, 2, ... vertices are 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. The index of each value list in the table starts at 1. An X indicates that the family in that row is not defined for the corresponding parameter value; infty denotes a disconnected graph.

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, 8, 21, 40, 65, 96, 133, ...
complete tripartite graph K_(n,n,n)A0941593, 18, 45, 84, 135, ...
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_(n,n)-MA033428infty, infty, 27, 48, 75, 108, 147, 192, 243, ...
cube-connected cycle graphA292028X, X, 888, 9472, 76160, 556032, 3605504, ...
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 graphA180861X, X, 8, 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_nA0855370, 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_nA122657X, X, 54, 256, 750, 1944, 4116, 8192, 14580, 25000, ...
transposition graphA2920620, 1, 21, 552, 19560, 920160, 55974240, ...
triangular graphA006011X, 0, 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, 6, 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). The parameters are positive integers, with additional restrictions indicated in the table.

Andrásfai graph1/2(3n-1)(5n-4)
antiprism graph n>=31/2(n+1)n^2
cocktail party graph K_(n×2) n>=22n^2
complete graph K_n1/2n(n-1)
2n-crossed prism graph n>=24n(n^2+2)
crown graph S_n^0 n>=33n^2
cycle graph C_n, n>=3{1/8n^3 for n even; 1/8(n-1)n(n+1) for n odd
gear graph n>=36n(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 ladder n>=31/4n[2n(n+2)-3-(-1)^n]
Mycielski graph M_n n>=21/(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 graph n>=3n(4n-5)
sunlet graph C_n circledot K_1 n>=31/4n[(-1)^n+2n(n+4)-5]
triangular graph n>=21/4n(n-1)^2(n-2)
wheel graph W_n n>=4(n-2)(n-1)

See also

Average Disorder Number, Balaban Index, Graph Distance Matrix, Graph Transmission, Kirchhoff Index, Mean Distance, Molecular Graph, Resistance Distance, Szeged Index, Topological Index, Transmission-Minimal Regular Graph, Vertex Transmission, Wiener Sum Index, Xu 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 Application." 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.03788v1.Hosoya, H. "Topological Index. A Newly Proposed Quantity Characterizing the Topological Nature of Structural Isomers of Saturated Hydrocarbons." Bull. Chem. Soc. Japan 44, 2332-2339, 1971.Knor, M.; Škrekovski, R.; and Tepeh, A. "Mathematical Aspects of Wiener Index." Ars Math. Contemp. 11, 327-352, 2016. https://doi.org/10.26493/1855-3974.795.ebf.Knor, M.; Škrekovski, R.; and Tepeh, A. "Chemical Graphs with the Minimum Value of Wiener Index." MATCH Commun. Math. Comput. Chem. 81, 119-132, 2019. https://match.pmf.kg.ac.rs/electronic_versions/Match81/n1/match81n1_119-132.pdf.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. Sequences A000217, A000290, A000292, A000567, A001105, A002378, A002411, A002697, A006011, A033428, A034828, A049598, A085537, A094159, A112851, A122657, A136328, A138179, A143945, A180574, A180576, A180857, A180861, A180863, A193217, A238419, A284039, A289022, A290004, A290129, A292018, A292022, A292025, A292026, A292028, A292029, A292036, A292039, A292040, A292044, A292045, A292051, A292053, A292054, A292055, A292056, A292057, A292058, A292059, A292061, and A292062 in "The On-Line Encyclopedia of Integer Sequences."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.Wiener, H. J. "Structural Determination of Paraffin Boiling Points." J. Amer. Chem. Soc. 69, 17-20, 1947.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 Resource. https://mathworld.wolfram.com/WienerIndex.html

Subject classifications