Generation of the eigenvectors of the topological matrix from graph theory

The technique of describing the characteristic polynomial of a graph is here extended to construction of the eigenvectors. Recurrence relations and path tracing are combined to generate eigenvector coefficients as polynomial functions of the eigenvalues. The polynomials are expressed as linear functions of Chebyshev polynomials in order to simplify the computational effort. Particular applications to the Hückel MO theory, including heteroatom effects, are shown.     

On the matching polynomials of graphs with small number of cycles of even length

Suppose that G is a simple graph. We prove that if G contains a small number of cycles of even length then the matching polynomial of G can be expressed in terms of the characteristic polynomials of the skew adjacency matrix A(G^e) of an arbitrary orientation G^e of G and the minors of A(G^e). In addition to a formula previously discovered by Godsil and Gutman, we obtain a different formula for the matching polynomial of a general graph. © 2005 Wiley Periodicals, Inc. Int J Quantum Chem, 2005     

Analysis of the topological dependency of the characteristic polynomial in its chebyshev expansion

The structural dependency (effect of branching and cyclisation) of an alternative form, the Chebyshev expansion, for the characteristic polynomial were investigated systematically. Closed forms of the Chebyshev expansion for an arbitrary star graph and a bicentric tree graph were obtained in terms of the “structure factor” expressed as the linear combination of the “step-down operator”. Several theorems were also derived for non-tree graphs. Usefulness and effectiveness of the Chebyshev expansion are illustrated with a number of examples. Relation with the topological index (Z _G ) was discussed. Operated for the U.S. Department of Energy by ISU under contract no. W-ENG-7405-82. Supported in part by the Office of Director     

The use of Frame’s method for the characteristic polynomials of chemical graphs

The evaluation of characteristic polynomials of graphs of any size is an extremely tedious problem because of the combinatorial complexity involved in this problem. While particular elegant methods have been outlined for this problem, a general technique for any graph is usually tedious. We show in this paper that the Frame method for the characteristic polynomial of a matrix is extremely useful and can be applied to graphs containing large numbers of vertices. This method reduces the difficult problem of evaluating the characteristic polynomials to a rather simple problem of matrix products. The coefficients in the characteristic polynomial are generated as traces of matrices generated in a recursive product of two matrices. This method provides for an excellent and a very efficient algorithm for computer evaluation of characteristic polynomials of graphs containing a large number of vertices without having to expand the secular determinant of the matrix associated with the graph. The characteristic polynomials of a number of graphs including that of a square lattice containing 36 vertices are obtained for the first time.     

Application of Maclaurin Series in Relating Interatomic Potential Functions: A Review

This paper provides a short review on the application of Maclaurin series in relating potential functions within the same category of interatomic interaction. The potential functions covered are those commonly adopted in computational chemistry softwares. While various mathematical approaches have been employed in generating relationships amongst potential functions, the use of Maclaurin series has been prevalent recently due to the increasing application of polynomial series-type potential functions. In the case of covalent bond-stretching, the Maclaurin series for the exponential function is used to transform the Morse potential into the polynomial series potential, and vice versa. For covalent bond-bending, Maclaurin series for the sine and cosine functions were employed to extract polynomial angle series potential from the Fourier series and harmonic cosine potential functions, and vice versa. Finally, both the exponential and the 1/(1 – x) expressions in Maclaurin series were used in obtaining the exact relationship for the repulsive terms between two potential functions.     

Evaluation of molecular moments by three methods

The three evaluative methods of the moment by means of the coefficient a_k of the HMO characteristic polynomial, the tree graph, and walk graph have been studied. © 2000 John Wiley & Sons, Inc. Int J Quant Chem 78: 237–244, 2000     

Graph theory of molecular orbitals beyond tight-binding approximation

The graph theory of molecular orbitals including second neighbor interactions (η) is considered here. Graphical methods of getting the characteristic polynomial for the π system of a conjugated molecule are given. It is shown that the characteristic polynomial can be factorized if there are symmetries in the molecule.     

On the evaluation of the characteristic polynomial of a chemical graph

The evaluation of the characteristic polynomial of a chemical graph is considered. It is shown that the operation count of the Le Verrier–Faddeev–Frame method, which is presently considered to be the most efficient method for the calculation of the characteristic polynomial, is of the order n⁴. Here n is the order of the adjacency matrix A or equivalently, the number of vertices in the graph G. Two new algorithms are described which both have the operation count of the order n³. These algorithms are stable, fast, and efficient. A related problem of finding a characteristic polynomial from the known eigenvalues λ_i of the adjacency matrix is also considered. An algorithm is described which requires only n(n ? 1)/2 operations for the solution of this problem.     

Topological dependency of the aromatic sextets in polycyclic benzenoid hydrocarbons. Recursive relations of the sextet polynomial

Mathematical meaning of the Clar's “aromatic sextet” is clarified by analysing the topological dependency of the sextet polynomial. Generalised recursive method for obtaining the sextet polynomial of a polyhex graph is presented. It is shown that the concept of the “super sextet” is necessarily introduced, if one-to-one correspondence between the Kekulé and sextet patterns is assumed. Topological dependency of the maximum number of resonant sextets is clarified and discussed in relation to the aromaticity and stability of polycyclic benzenoid hydrocarbons.     

On evaluation of the characteristic polynomial for large molecules

Existing schemes for evaluation of the characteristic polynomial of a graph suffer from limited practicality. Their application to large molecules inordinately increases the amount of labor. Here a procedure is outlined which is useful even for large molecules. It is based on a not widely known property of the collection of characteristic polynomials for Ulam's subgraphs, which, when added, give the derivative of the characteristic polynomial of the initial graph. The characteristic polynomials for Ulam's subgraphs are, as a rule, easier to derive due to the presence of many pending bonds in graphs of chemical interest. The last step requires an integration of a polynomial (which is a straightforward step) and determining the constant of integration, which represents the determinant of the adjacency matrix. The available methods for determing the additive constant (the determinant) are combinatorially much simpler than the initial task of finding all of the coefficients of the characteristic polynomial. The approach is illustrated on selected benzenoid hydrocarbons, nonbenzenoid, and nonalternant systems. Construction of the characteristic polynomials can be accelerated by considering auxiliary fragments and irreducible subgraphs separately and combining them in the final expression. Many auxiliary fragments allow their characteristic polynomials to be expressed in a closed form using recursive relations. The results for complex molecules can thus be written in a relatively compact form. Finally, the derivative of the characteristic polynomial, expressed in terms of selected auxiliary functions and irreducible components, can be integrated directly to give the result in terms of contributions signifying various fragments rather than as an explicit function of x.     

Immanants and immanantal polynomials of chemical graphs

The much-studied determinant and characteristic polynomial and the less well-known permanent and permanental polynomial are special cases of a large class of objects, the immanants and immanantal polynomials. These have received some attention in the mathematical literature, but very little has appeared on their applications to chemical graphs. The present study focuses on these and also generalizes the acyclic or matching polynomial to an equally large class of acyclic immanantal polynomials, generalizes the Sachs theorem to immanantal polynomials, and sets forth relationships between the immanants and other graph properties, namely, Kekulé structure count, number of Hamiltonian cycles, Clar covering polynomial, and Hosoya sextet polynomial.     

Characteristic polynomials of chemical graphs via symmetric function theory

The characteristic polynomial corresponding to the adjacency matrix of a graph is constructed by using the traces of the powers of the adjacency matrix to calculate the coefficients of the characteristic polynomial via Newton's identities connecting the power sum symmetric functions and the elementary symmetric functions of the eigenvalues. It is shown that Frame's method, very recently employed by Balasubramanian, is nothing but symmetric functions and Newton's identities.     

Application of molecular orbital graph theory to vibrational problems of finite chain systems

A generating function approach based on molecular orbital graph theory is presented that provides a straightforward way of obtaining the secular polynomials and energy bands for repeated unit systems from polynomial recurrence expressions. The possibility of obtaining the analytical energy-level spectrum of the system can also be predicted. These results are then used to discuss the vibrational problems of finite chain systems with single- and double-component lattices. It seems to be the first report describing the vibrational states of an (AB)_N chain.     

On alternative form of the characteristic polynomial and the problem of graph recognition

The characteristic polynomial of a structure (molecule or a graph) is usually expressed as a function ofx. Here we explore an alternative representation of characteristic polynomials expressed in terms ofL _n , the characteristic polynomials of linear chains havingn atoms. While the new forms of the characteristic polynomials are mathematically equivalent to the old forms, they appear to reflect selected structural similarities among homologous molecules better. Besides arriving at general expressions for the form of the characteristic polynomials for numerous families of compounds previously unavailable, the approach is of some interest for the old problem of graph isomorphism and graph recognition in cases of structures which can be associated with a homologous series.     

Study of the origin of subspectrality in molecular graphs

Summary The subspectral origin of three families of molecules based on cyclobutadiene, benzene, and cyclooctatetraene is discussed. The graph theoretical decomposition of the fourfold cyclooctatetraene molecular graphs is presented in explicit form and has expedited the computation of their respective eigenvalues. The cyclic automorphism approach of Davidson is clarified and merged with the author's methodology leading to a more comprehensive procedure for rapidly determining the characteristic polynomial and eigenvalues of chemically significant molecular graphs. The graph theoretical determination of the characteristic polynomials and eigenvalues of two sixfold coronene-related molecular families is presented.     

Computer generation of matching polynimials of chemical graphs and lattices

A computer program in Pascal is developed for computing the matching polynomials of graphs and lattices. This program is based on the recursive relation for matching polynomials outlined by Hosoya [Bull. Chem. Soc. Jpn., 44 , 2332 (1971)], Gutman and Hosoya [Theor. Chim. Acta, 48 , 279 (1978)], and others. The graph whose matching polynomial is of interest is reduced recursively until the graph reduces to several trees. The characteristic polynomial of a tree is the same as the matching polynomial. The characteristic polynomials of resulting trees are computed using the computer program based on Frame's method developed by Balasubramanian [Theor. Chim. Acta, 65 , 49 (1984)]; J. Comput. Chem., 5 , 387 (1984). The resulting polynomials are then assembled to compute the matching polynomial of the initial graph. The program is especially useful in generating the matching polynomials of graphs containing a large number of vertices. The matching polynomials thus generated are potentially useful in several applications such as lattice statistics (dimer covering problem), aromaticity, valence bond methods (enumeration of perfect matchings) in the calculation of grand canonical partition functions, in the computation of thermodynamic properties of saturated hydrocarbons, and in chemical documentation.     

Construction of characteristic polynomial of reciprocal graphs from the number of pendant vertices

A method for construction of the characteristic polynomial (CP) coefficients of the three classes of reciprocal graphs, viz., L_n + n(p), C_n + n(p), and K_1,n?1 + n(p), has been developed that requires only the value of n. The working formulas have been expressed in matrix product form, computer programs for which can easily be developed. © 2004 Wiley Periodicals, Inc. Int J Quantum Chem, 2005     

Generalized Hosoya polynomials of hexagonal chains

Similar to the well-known Wiener index, Eu et al. [Int. J. Quantum Chem. 106 (2006) 423–435] introduced three families of topological indices including Schultz index and modified Schultz index, called generalized Wiener indices, and gave the similar formulae of generalized Wiener indices of hexagonal chains. They also mentioned three families of graph polynomials in x, called generalized Hosoya polynomials in contrast to the (standard) Hosoya polynomial, such that their first derivatives at x = 1 are equal to generalized Wiener indices. In this note we gave explicit analytical expressions for generalized Hosoya polynomials of hexagonal chains.