How to compute the Wiener index of a graph

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.     

Wiener indices of trees and monocyclic graphs with given bipartition

The Wiener index of a connected graph is defined as the sum of distances between all unordered pairs of its vertices. It has found various applications in chemical research. We determine the minimum and the maximum Wiener indices of trees with given bipartition and the minimum Wiener index of monocyclic graphs with given bipartition, respectively. We also characterize the graphs whose Wiener indices attain these values. © 2011 Wiley Periodicals, Inc. Int J Quantum Chem, 2012     

Graphs of unbranched hexagonal systems with equal values of the wiener index and different numbers of rings

Graphs of unbranched hexagonal systems consist of hexagonal rings connected with each other. Molecular graphs of unbranched polycyclic aromatic hydrocarbons serve as an example of graphs of this class. The Wiener index (or the Wiener number) of a graph is defined as the sum of distances between all pairs of its vertices. Necessary conditions for the existence of graphs with different numbers of hexagonal rings and equal values of the Wiener index are formulated, and examples of such graphs are presented.     

直链烷烃取代衍生物Wiener指数的简便计算方法

根据直链烷烃衍生物分子拓扑结构的特点,将直链烷烃衍生物拆分为由直链单元和取代基团几个部分构成,再根据每部分的拓扑结构特点给出相应的计算公式.从而提出了一个计算直链烷烃衍生物Wiener指数的简便方法,达到简化计算的目的.该方法简化了传统Wiener指数的计算方法,使Wiener指数的计算具有效率高、不易出错等优点,便于Wiener指数计算程序化,从而提高了Wiener指数的实用性.     

Generalized Wiener indices in hexagonal chains

The Wiener index, or the Wiener number, also known as the “sum of distances” of a connected graph, is one of the quantities associated with a molecular graph that correlates nicely to physical and chemical properties, and has been studied in depth. An index proposed by Schultz is shown to be related to the Wiener index for trees, and Ivan Gutman proposed a modification of the Schultz index with similar properties. We deduce a similar relationship between these three indices for catacondensed benzenoid hydrocarbons (graphs formed of concatenated hexagons, or hexagonal chains, or sometimes acenes). Indeed, we may define three families of generalized Wiener indices, which include the Schultz and Modified Schultz indices as special cases, such that similar explicit formulae for all generalized Wiener indices hold on hexagonal chains. We accomplish this by first giving a more refined proof of the formula for the standard Wiener index of a hexagonal chain, then extending it to the generalized Wiener indices via the notion of partial Wiener indices. Finally, we discuss possible extensions of the result. © 2005 Wiley Periodicals, Inc. Int J Quantum Chem, 2006     

Bounds on Harary index

In this paper, we obtain the lower and upper bounds on the Harary index of a connected graph (molecular graph), and, in particular, of a triangle- and quadrangle-free graphs in terms of the number of vertices, the number of edges and the diameter. We give the Nordhaus–Gaddum-type result for Harary index using the diameters of the graph and its complement. Moreover, we compare Harary index and reciprocal complementary Wiener number for graphs.     

Combinatorial models and algorithms in chemistry. The expanded Wiener number—a novel topological index

An expanded form of the Wiener number is suggested for characterization of molecular graphs and structure-property correlations. The simple, computer-oriented method for counting of the novel index is briefly discussed.     

An approach to automated partial structure expansion

An algorithm (ASSEMBLE) to construct all structures consistent with the structural implications of the chemical and spectroscopic properties of an unknown molecule is described. The design of ASSEMBLE takes cognizance of the need to supply some nonoverlapping substructure information in addition to the molecular formula, and the use of structural constraints that cannot be directly expressed as non-overlapping fragments. ASSEMBLE employs several heuristics (rules) intended to avoid the assembly of identical (isomorphic) graphs. To provide a non-redundant list of structures, duplicate structures are recognized and removed by a naming algorithm. ASSEMBLE also perceives different π-resonance forms as identical structures even when they are topologically non-equivalent.     

The Mean Isomer Degeneracy of the Wiener Index

The mean isomer degeneracy of the Wiener index was previously shown to become unboundedly large as n (the number of vertices of the molecular graphs of the isomers considered) increases. We here show that there is a high isomer degeneracy in the case of molecules of medium size, namely when n = 6 and n = 7.     

On reciprocal reverse Wiener index

We report some properties, especially bounds for the reciprocal reverse Wiener index of a connected (molecular) graph. We find that the reciprocal reverse Wiener index possesses the minimum values for the complete graph in the class of n-vertex connected graphs and for the star in the class of n-vertex trees, and the maximum values for the complete graph with one edge deleted in the class of n-vertex connected graphs and for the tree obtained by attaching a pendant vertex to a pendant vertex of the star on n − 1 vertices in the class of n-vertex trees. These results are compared with those obtained for the ordinary Wiener index.     

Molecular cyclicity and centricity of polycyclic graphs. I. Cyclicity based on resistance distances or reciprocal distances

Rules for molecular cyclicity based on the global indices resulting from reciprocal distances (Harary number, H) or from resistance distances (Kirchhoff number, Kf) were tested in comparison with those elaborated earlier by means of the Wiener index, W. The Harary number and the Wiener number were found to match molecular cyclicity in an almost identical manner. The Kirchhoff number also generally follows cyclicity trends described previously. H is slightly less degenerate than is W, but Kf has practically no degeneracy in the graphs investigated here. Being much more discriminating than the Wiener number (i.e., practically nondegenerate), Kf allowed the formulation of new rules for systems formed from linearly condensed ribbons of even-membered rings with different sizes as well as for branched ribbons. The topological cyclicity patterns are thus reformulated in an extended basis, proceeding from three different graph metrics. © 1994 John Wiley & Sons, Inc.     

Graph theory and molecular orbitals

A simple algorithm for the determination of the number of zeros in the molecular graphs of alternant cata-condensed conjugated hydrocarbons is derived. For non-branched hydrocarbons it is shown that, from the topological point of view, only four types of ring systems exist. The given algorithm enables the derivation of a number of general regularities relating the structural features of the molecule with its stability.     

Algorithm for naming molecular equivalence classes represented by labeled pseudographs

The emergence of large chemical databases imposes a need for organizing the compounds in these databases. Mapping the chemical graph in particular, and a molecular equivalence class represented by a labeled pseudograph in general, to a unique number or string facilitates high-throughput browsing, grouping, and searching of the chemical database. Computing this number using a naming adaptation of the Morgan algorithm, we observed a large classification noise in which nonisomorphic graphs were mapped to the same number. Our extensions to that algorithm greatly reduced the classification noise.     

Heuristics for similarity searching of chemical graphs using a maximum common edge subgraph algorithm

Recently a method (RASCAL) for determining graph similarity using a maximum common edge subgraph algorithm has been proposed which has proven to be very efficient when used to calculate the relative similarity of chemical structures represented as graphs. This paper describes heuristics which simplify a RASCAL similarity calculation by taking advantage of certain properties specific to chemical graph representations of molecular structure. These heuristics are shown experimentally to increase the efficiency of the algorithm, especially at more distant values of chemical graph similarity.