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.     

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.     

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     

On the evaluation of the characteristic polynomial via symmetric function theory

The use of power sum symmetric functions leads to Newton's identities, which relate the traces of various powers ofA, the adjacency matrix of a graph, and the coefficients of the characteristic polynomials. While it is possible to solve Newton's identities and generate the coefficients by recursion or, alternatively, to derive them by sequential manipulations (yielding the explicit formulas), we show how the results can be expressed using a combinatorial approach and relate the evaluation of the coefficients to selected Young diagrams.     

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.     

Computing the characteristic polynomial of a tree

An algorithm is given for computing the values of the characteristic polynomial of a tree. Its time complexity is linear; hence, the polynomial is readily accessible from the tree and no computation is necessary to get the polynomial ready for applications. If necessary, the coefficients can be determined in time O(n ²). This improves the complexity O(n ³), reached by Tinhofer and Schreck, to O(1).received by the Publisher 20 September 1989This work was supported in part by the Research Council of Slovenia, Yugoslavia.     

Graphs corresponding to reference polynomial or to circuit characteristic polynomial

A vertex-weighted graphG ^* is studied which is obtained by deleting edgee _rs in a circuit of a graphG and giving two vertices _r and _s weightsh _r = 1 andh _s = -1, respectively. It is shown that if subgraphG - _r is identical with subgraphG - _s, then the reference polynomial ofG ^* is identical with that ofG and the characteristic polynomial ofG ^* contains the contributions due to only a certain part of the circuits found in the original graphG. This result gives a simple way to find a graph whose characteristic polynomial is equal to the reference polynomial in the topological resonance energy theory or to the circuit characteristic polynomial in the circuit resonance energy theory. This approach can be applied not only to Hilckel graphs but also to Möbius graphs, provided that they satisfy a certain condition. The significances of this new type of reference graph thus obtained are pointed out.     

The characteristic polynomial of a chemical graph

We list uses of, and the computational methods for the characteristic polynomial of a (chemical) graph. Pour computational methods are singled out for more detailed presentation. These are the graphical methods of Sachs, the recurrence formulae for several classes of simple graphs, the method based on Ulam subgraphs, and the Le Verrier — Faddeev — Franic recursive method. The latter method appears, at present, to be the most efficient procedure for the computation of the characteristic polynomials of graphs of sizes with up to even a few hundred sites.Dedicated to Dennis H. Rouvray, the friend and one of the foremost popularizers of chemical graph theory in our time.Research supported by the Robert A. Welch Foundation of Houston, Texas, USA.     

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.     

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     

Properties and derivation of the fourth and sixth coefficients of the characteristic polynomial of molecular graphs—New graphical invariants

Some previously unknown relationships for determining the a ₄ and a ₆ coefficients of the characteristic polynomial for polycyclic aromatic hydrocarbons are presented for the first time. The structural information contained in these coefficients is more fully revealed. The equations derived for a ₄ and a ₆ allow one to determine the characteristic polynomial by inspection for many small molecular graphs. Some relationships for a ₈ and a ₁₀ are presented. The set of known graphical invariants (GI) or properties that remain unchanged in isomeric PAH6s is now shown to be GI={a ₄, a ₆+n ₀+2r ₆, a ₈ ^c , d _s+N_Ic, N_c, N_h, N_Ic+N_Pc, q, r}.Part VIII: A periodic table for polycyclic aromatic hydrocarbons     

Computing the maximal canonical form for trees in polynomial time

Known algorithms computing a canonical form for trees in linear time use specialized canonical forms for trees and no canonical forms defined for all graphs. For a graph \(G=(V,E)\) the maximal canonical form is obtained by relabelling the vertices with \(1,\ldots ,|V|\) in a way that the binary number with \(|V|^2\) bits that is the result of concatenating the rows of the adjacency matrix is maximal. This maximal canonical form is not only defined for all graphs but even plays a special role among the canonical forms for graphs due to some nesting properties allowing orderly algorithms. We give an \(O(|V|^2)\) algorithm to compute the maximal canonical form of a tree.     

Parallel algorithm for the computation of characteristic polynomials of chemical graphs

A parallel algorithm is developed for the first time based on Frame's method to compute the characteristic polynomials of chemical graphs. This algorithm can handle all types of graphs: ordinary, weighted, directed, and signed. Our algorithm takes only linear time in the CRCW PRAM model with O(n³) processors whereas the sequential algorithm takes O(n⁴) time. Especially when the number of vertices of the graph is large this method will be more efficient than the recently developed vectorized Frame and Givens–Householder methods.     

Coulson function and Hosoya index: extension of the relationship to polycyclic graphs and to new types of matching polynomials

Gutman et al. [Chem. Phys. Lett. 355 (2002) 378–382] established a relationship between the Coulson function, , where \phi is the characteristic polynomial, and the Hosoya index Z, which is the sum over all k of the counts of all k-matchings. Like the original Coulson function, this relationship was postulated only for trees. The present study shows that the relationship can be extended to (poly)cyclic graphs by substituting the matching, or acyclic, polynomial for the characteristic polynomial. In addition, the relationship is extended to new types of matching polynomials that match cycles larger than edges (2-cyc1es). Finally, this presentation demonstrates a rigorous mathematical relationship between the graph adjacency matrices and the coefficients of these polynomials and describes computational algorithms for calculating them.     

On the Coulson integral formula for total π-electron energy

The Coulson integral formula for total π-electron energy (E_π) is analysed, and an elementary derivation of it is presented. Three novel Coulson-type formulae are obtained and one is used for deriving the McClelland (approximate) expression for E_π. An approximation of a particular formula is proposed which results in a linear relationship between E_π and the coefficients of the characteristic polynomial of the molecular graph.     

Coefficient interrelatedness among polynomial potential functions of diatomic molecules

It is shown that the diatomic potential energy functions of Dunham, SPF and Ogilvie can be easily converted from one another when their coefficients are related. Through Maclaurin expansion and comparison of terms, the coefficients can be related by using the Pascal Triangle. In this paper, the coefficients were related up to the tenth order of δr/R for HX (X = H, Ga, Cl, I). Comparison of all three potential energy curves shows very good agreement for r ≤ 1.5R, thereby verifying the formulated relations. Observation of the plotted potential energy curves for r > 1.5R shows that the difference of the three potential function definitions is not reflected as any consistent trend arising from the related potential functions.     

On the matching properties of three fence graphs

Supplementing the construction of a Möbius ladder graph derived from a ladder graph, the linear fence graph and cyclic fence graph are introduced. These have neater mathematical expressions for the perfect matching numbers and the matching and characteristic polynomials than the graphs in the previous families.     

A graphical evaluation of characteristic polynomials of huckel trees

Characteristic polynomials of acyclic carbon chains (Huckel trees) are treated in a systematic way. Formulas of coefficients (a_k) of the polynomial are obtained in terms of connectivities that were introduced for dealing with moments in a previous paper. Based on the meaning of a_k, a graph-theoretical analysis is given such that a_k can be expressed as a linear combination of binomial factors specified by a set of graphs containing ½k edges. The numerical relationship is disclosed between each binomial factor and its specified graph. This stimulates the proposal of a novel approach for evaluating ak by simply collecting the graph set of defnite edges. The approach is equally applicable for the evaluation of matching polynomials of cyclic systems and extendable to the investigation of general trees.     

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.     

Calculation of the coefficients of the characteristic polynomial from its subgraphs

The characteristic polynomial associated with π-electrons of conjugated molecules are discussed by using subgraphs derived from molecular graphs as a basis for their construction. A practical method has been developed for evaluating the coefficient a_K of conjugated molecules. Applying this method, the general formulas of evaluating the coefficient a_K for homologous conjugated molecules have been obtained. The approach is illustrated on a few simple conjugated systems, including also a few polymeric systems. © 1996 John Wiley & Sons, Inc.