How to compute the Wiener index of a graph |
| |
Authors: | Bojan Mohar Tomaž Pisanski |
| |
Affiliation: | (1) Department of Ma theima tics, University E.K. of Ljubljana, Jadranska 19, 61111 Ljubljana, Yugoslavia;(2) Department of Mathematics and Statistics, Simon Fraser University, Burnaby, B. C., Canada |
| |
Abstract: | The Wiener index of a graphG is equal to the sum of distances between all pairs of vertices ofG. It is known that the Wiener index of a molecular graph correlates with certain physical and chemical properties of a molecule. In the mathematical literature, many good algorithms can be found to compute the distances in a graph, and these can easily be adapted for the calculation of the Wiener index. An algorithm that calculates the Wiener index of a tree in linear time is given. It improves an algorithm of Canfield, Robinson and Rouvray. The question remains: is there an algorithm for general graphs that would calculate the Wiener index without calculating the distance matrix? Another algorithm that calculates this index for an arbitrary graph is given. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|