Molecular graph polynomials

The number of vertices and edges in a molecular graph are examples of simple topological indices. More complex structural descriptors were presented in Section 7 on molecular matrices and Section 8 on molecular graph polynomials. We mention here some of the most used topological indices the Wiener W index the Randid connectivity index x extended by Kier and Hall the Hosoya Z index and the Balaban J index. > ... 

Molecular graph polynomials which can be obtained from matrices associated with molecular graphs provide useful information, e.g., on the number of Kekul6 structures in polycyclic aromatic compounds. Spectra of graphs are the corresponding eigenvalues, and these may be associated with energy levels as in HMO theory, or with structural invariants. 

Dias, J.R. (1987b). Facile Calculations of Select Eigenvalues and the Characteristic Polynomial of Small Molecular Graphs Containing Heteroatoms. Can.J.Chem., 65, 734-739. 

Faulon, J.-L. (1998). Isomorphism, Automorphism Partitioning, and Canonical Labeling Can Be Solved in Polynomial-Time for Molecular Graphs. J.Chem.lnf.Comput.Scl, 38,432-444. 

Ivanciuc, O. (1993). Chemical Graph Polynomials. Part 3. The Laplacian Polynomial of Molecular Graphs. Rev.Roum.Chim., 38,1499-1508. 

A large number of characteristic polynomial-based descriptors and spectral indices are defined in literature, to study both molecular graphs and model physico-chemical properties of molecules. 

The characteristic polynomial of the molecular graph is the characteristic polynomial of a graph-theoretical matrix M derived from the graph [Graham and Lovasz, 1978 Diudea, Ivanciuc et al, 1997 Diudea, Gutman et al, 2001 Ivanciuc, 2001c] ... 

A large number of graph polynomials were proposed in the literature, which differ from each other according to the molecular matrix M they are derived from, and the weighting scheme w used to characterize heteroatoms and bond multiplicity of molecules. 

The distance polynomial is the characteristic polynomial of the distance matrix D of the molecular graph [Hosoya, Murakami et al, 1973 Graham, Hoffman et al, 1977 Graham and Lovasz, 1978] ... 

Characteristic polynomials belong to a more general class of graph polynomials, which are used to encode some information on molecular graphs. Among these, there are Z-counting polynomial, —> matching polynomial, and Wiener polynomial. 

The Altenburg polynomial is another example of counting polynomials defined for H-depleted molecular graph Q as... 

In general, coefficients, roots, and derivatives of counting polynomials can be used for characterization of molecular graphs and as molecular descriptors in QSAR/QSPR modeling. 

Faulon, J.-L. (1998) Isomorphism, automorphism partitioning, and canonical labeling can be solved in polynomial-time for molecular graphs. J. Chem. Inf. Comput. Sci., 38, 432-444. 

Gutman, L, Graovac, A. and Mohar, B. (1982) On the existence of a Hermitian matrix whose characteristic polynomial is the matching polynomial of a molecular graph. MATCH Commun. Math. Comput. Chem., 13, 129-150. 

The propagation diagram algorithm for the computation of the characteristic polynomial of molecular graphs. Rev. Roum. Chim., 37, 1341-1345. 

Ivanduc, O., Ivanduc, T. and Diudea, M.V. (1999b) Polynomials and spectra of molecular graphs. Roum. Chem. Quart. Rev., 7, 41—67. 

Huckel molecular orbitsd theory and related simple one-electron models axe concerned with the topdogy of conjugated molecules. The characteristic polynomial of the molecular graph functions in this context as the secular determinant. For more details on this topic see the chapter Graph Theory and Molecular Orbitals by Professor N. Trinajstii in this volume. 

Details of the extensive recent work on characteristic pdynomials can be found elsewhere [157,18S-185], In a series of papers [186-189] Dias examined some structural invariants of the molecular graph, related to the coefficients of the characteristic polynomial and having chemical significance. Various methods for the computation of the characteristic polynomials of chemical graphs have been put forward [190-194]. The factorization of the characteristic polynomials was studied by Kirby [195]. In the present moment (January 1989) it seems that the characteristic polynomial still remains the most popular among graphic polynomials of mathematical chemistry. 

The next discoverer of the matching polynomial was Hosoya [43,44], who considered the polynomial Af(G,x) of the molecular graph of a saturated hydrocarbon. In particular, Hosoya noticed that the total number of matchings in G, namely... 

For any pD-model p 3), we can develop descriptors of variable dimensionality d. Examples of zero-dimensional descriptors are single numbers such as the radius of gyrationio (used for OD, ID, and 2D models) or the molecular volume 1 (used for 2D models). One-dimensional descriptors such as radial distribution functions or knot polynomials are used in OD and ID models, respectively. Two-dimensional descriptors include distance maps and Rama-chandran torsional-angle maps for some OD and ID models. Similarly, molecular graphs (2D descriptors) can be associated with ID models (contour lines), 2D models (molecular surfaces), or 3D models (e.g., the entire electron density function). Shape descriptors of higher dimensionality can also be constructed. 

---