Counting of Paths

FIGURE 2.22 Count of paths for three symmetry nonequivalent carbon atoms of norbomane. 

When the above are multiplied by 4, 2, and 1, respectively, so as to include the contributions from symmetry equivalent vertices, and added, one obtains the path count for the norbomane molecule, which is 16, 22, 28, 36, 28, 12. This has to be divided by 2, because each path has been counted twice, which gives 8,11,14, 18, 14, 6. This gives for the total number of paths in norbomane 71. The path numbers 8, 11, 14, 18, 14, 6, and the total number of paths, 71, clearly do not depend on how one labels the vertices of norbomane or how one depicts the carbon skeleton of norbomane and thus represent invariants. Graph invariants can be used as molecular descriptors or as parameters in quantitative comparative studies of molecules. Whether they will remain mere mathematical constructions or they will become chemically useful descriptors, can only be established after they have been tested on a number of stracture-property correlations. We will address this topic in more detail in the following chapters and will examine closely a collection of more widely used ( popular ) molecular descriptors. 

In Table 2.2, we have shown, in addition to the adjacency matrix A, the distance matrix D, also the valence matrix V, the Laplacian matrix L, and the powers and A of the adjacency matrix, all for norbomane. Distance matrix D of a graph, another useful matrix in chemical graph theory, was introduced by F. Harary [118], The element [D] , of the D matrix are defined as 

---

Moreover, the Wiener difference matrix Wa was also proposed as Wa = W — W, whose off diagonal elements are based on path contributions calculated only on paths larger than 1 [ Diudea, 1996a, 1996b Ivanciuc, Ivanciuc et al., 1997]. By applying the Wiener operator to the Wiener difference matrix, Wiener-type indices are obtained that are based on counts of paths larger than 1. 

In the approach leading to kappa shape indexes, it is necessary to transform "P into an index that carries information for any number of atoms in the molecule. To accomplish this, we define a particular shape attribute as having an intermediate relationship between two extreme shapes, each of which may be defined both pictorially and numerically. We take the position, for the present, that these extreme shapes must be common to subsets of molecules of any number of atoms. The extremes selected for any order of attribute, m, are the maximum, "Pmax and minimum, " P, in, counts of paths in the molecular graphs of molecules with a common atom count. A shape attribute of a particular order, m, for a particular molecule, i, is therefore... 

Therefore, it is not surprising that two molecules can have the same count of paths of different length. For example, 2,3,4-trimethylhexane and 3-methyl-3-ethylhexane, (two isomers of nonane) have the same path counts (9, 8, 10, 10, 6, 2). ... 

To select the most similar structures by inspection is somewhat risky. Are n-octane and 2-methylheptane the most similar, or 2-methyloctane and 3-methylheptane, or some other such pair The use of the quantitative approach is therefore important when the similarity is not apparent, as is frequently the case. However, in this particular quantitative application, we see somewhat disappointingly from Table 2 that in all there are 20 pairs of isomers emerging as equally most similar The smallest entry in the similarity/dissimilarity table (1.4142) occurs whenever path sequences differ by a single entry. Though the count of paths is distinct for each isomer, clearly the characterization by paths fails to discriminate the structures sufficiently well. Is this... 

Enumerating structures with molecular descriptors. Enumerating molecules matching molecular descriptors or topological descriptors is a longstanding problem. Surprisingly, few reports in the literature provide answers to the question. Most of the proposed techniques are stochastic in nature and are reviewed in the Sampling Structures section. In a series of five papers, Kier, et reconstruct molecular structures from the count of paths... 

Simultaneous with the work from Kier and Hall, Zefirov et al. developed a similar technique with the count of paths. The QSARs they used were given for three Kappa-shape descriptors and they considered three functional groups, namely, alkanes, alcohols, and small oxygen-containing compounds. 

The count of paths of three contiguous bonds, P, forms the basis for the quantitation of another shape attribute. This structure is compared to two extreme structures, P ax and Pmin- For the third-order attribute P ax is chosen to be a twin star structure shown in Table 6, no. 5. For P in the linear graph, Table 6, no.6 is the representation when = 8. In general, for any odd value of A, P ax = A — ) A — 3)/4, and for any even value of A, P ax = A — 2) /4. In general, P in = — 3. A suitable algorithm in which third-order shape information can be encoded from Pj- is given in equation 11. 

P and the count of paths and of paths of length I, rings and rings the count of rings and of rings of size/. 

For the functional groups at the chain ends, the counting of paths is slightly different. In particular for the polymers carrying the functional groups at both ends, there remain no free ends in the completion of reaction a 1, and hence Vend 0. 

The nonzero elements of this matrix represent counts of paths larger than unity. The Wiener difference matrix for Tj (see Figure 2.19) is exanplified below ... 

Let us return briefly to introduce the shape indices of Randic [28], which are calculated for individual vertices as the ratio of the number of paths of length k and the number of walks of length k. Consider 3-methylhexane (Figure 6.1) for illustration of paths of length k = 2 and fe = 3. It is not difficult to count the paths in acyclic graphs. In Table 6.5, we show the counts of paths and walks of lengths two and three for 3-methylhexane. As the result for 3-methylhexane CyHig one obtains (P2/W2) = 3.5000 and (P3/W3) = 1.87024. 

More than 65 years ago, J. R. Platt [46] suggested the count of paths of different lengths in molecules as a tool for numerical characterization of molecules. The suggestion by Platt is that the sequences of path numbers are the language of interest in comparative study of chemical structures. For some, such a proposition may appear to be a chemically futile mathematical exercise that may entertain some. In the central column of Table 7.1, we show the result of such a mathematical exercise, which offers a numerical representation of octane isomers. For example, 2,3-dimethyhexane... 

---