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.     

Computer generation of characteristic polynomials of edge-weighted graphs,heterographs, and directed graphs

The computer code developed previously (K. Balasubramanian, J. Computational Chem., 5 , 387 (1984)) for the characteristic polynomials of ordinary (nonweighted) graphs is extended in this investigation to edge-weighted graphs, heterographs (vertex-weighted), graphs with loops, directed graphs, and signed graphs. This extension leads to a number of important applications of this code to several areas such as chemical kinetics, statistical mechanics, quantum chemistry of polymers, and unsaturated systems containing heteroatoms which include bond alternation. The characteristic polynomials of several edgeweighted graphs which may represent conjugated systems with bond alternations, heterographs (molecules with heteroatoms), directed graphs (chemical reaction network), and signed graphs and lattices are obtained for the first time.     

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.     

Computer generation of spectra of graphs: Applications to C60 clusters and other systems

A computer code based on the Givens–Householder matrix diagonalization method is used to calculate the spectra of graphs containing a large number of vertices. The code is most general in that it can handle graphs containing 200 or more vertices. Further, the code can be used to generate the spectra of weighted graphs. The program requires as input only the neighborhood table of the graph. The spectra of many graphs are generated for the first time in less than a few minutes of computer time. Applications to a number of chemical systems including two forms (foot and hand) of the recently synthesized C₆₀ cluster and the effect of bond alternation on these systems are discussed. In addition, the spectra of square and honeycomb lattices and the characteristic polynomials of the foot and hand forms of the C₆₀ cluster are obtained.     

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.     

Computer generation of the characteristic polynomials of chemical graphs

A computer program based on the Frame method for the characteristic polynomials of graphs is developed. This program makes use of an efficient polynomial algorithm of Frame for generating the coefficients in the characteristic polynomials of graphs. This program requires as input only the set of vertices that are neighbors of a given vertex and with labels smaller than the label of that vertex. The program generates and stores only the lower triangle of the adjacency matrix in canonical ordering in a one-dimensional array. The program is written in integer arithmetic, and it can be easily modified to real arithmetic. The coefficients in the characteristic polynomials of several graphs were generated in less than a few seconds, thus solving the difficult problem of generating characteristic polynomials of graphs. The characteristic polynomials of a number of very complicated graphs are obtained including for the first time the characteristic polynomial of an honeycomb lattice graph containing 54 vertices.     

Computational algorithms for matching polynomials of graphs from the characteristic polynomials of edge-weighted graphs

Computational algorithms are described which provide for constructing the set of associated edge-weighted directed graphs such that the average of the characteristic polynomials of the edge-weighted graphs gives the matching polynomial of the parent graph. The weights were chosen to be unities or purely imaginary numbers so that the adjacency matrix is hermitian. The computer code developed earlier by one of the authors (K.B.) is generalized for complex hermitian matrices. Applications to bridged and spirographs, some lattices and all polycyclic graphs containing up to four cycles are considered.     

Recent developments in tree-pruning methods and polynomials for cactus graphs and trees

The object of this paper is to review the recent developments in tree-pruning methods and characteristic and matching polynomials of spirographs, cacti and trees. The applications of the pruning method to spirographs, Bethe lattices, cactus lattices and Bethe cactus lattices are considered. In each case, the tree-pruning method yields analytical solutions for these graphs.Camilee and Henry Dreyfus Teacher-Scholar.     

The characteristic polynomials of structures with pending bonds

It is well known [1] that the calculation of characteristic polynomials of graphs of interest in Chemistry which are of any size is usually extremely tedious except for graphs having a vertex of degree 1. This is primarily because of numerous combinations of contributions whether they were arrived at by non-imaginative expansion of the secular determinant or by the use of some of the available graph theoretical schemes based on the enumeration of partial coverings of a graph, etc. An efficient and quite general technique is outlined here for compounds that have pending bonds (i.e., bonds which have a terminal vertex). We have extended here the step-wise pruning of pending bonds developed for acyclic structures by one of the authors [2] for elegant evaluation of the characteristic polynomials of trees by accelerating this process, treating pending group as a unit. Further, it is demonstrated that this generalized pruning technique can be applied not only to trees but to cyclic and polycyclic graphs of any size. This technique reduces the secular determinant to a considerable extent. The present technique cannot handle only polycyclic structures that have no pending bonds. However, frequently such structures can be reduced to a combination of polycyclic graphs with pending bonds [3] so that the present scheme is applicable to these structures too. Thus we have arrived at an efficient and quite a simple technique for the construction of the characteristic polynomials of graphs of any size.     

Moments and characteristic polynomials for square lattice graphs

The method of moments is used to derive closed analytical expressions for the characteristic polynomials of square lattice graphs. We obtain exact analytical formulae for three-dimensional cubic lattices, square lattices, tubular square lattices, and cylindrical square lattices containing any number of vertices.Camille and Henry Dreyfus Teacher-Scholar.     

Characteristic polynomials of spirographs

A class of graphs called spirographs is defined. It is shown that the characteristic polynomials of spirographs can be obtained in terms of the characteristic polynomials of smaller graphs by pruning the spirographs at the spiral points. Elegant recursive relations are derived for many spirographs. Characteristic polynomials of branched spirographs are also obtained.Alfred P. Sloan Fellow; Camille and Henry Dreyfus Teacher-Scholar.     

Exact dimer statistics and characteristic polynomials of cacti lattices

Summary The pruning method developed earlier by one of the authors (K.B.) combined with the operator method is shown to yield powerful recursive relations for generating functions for dimer statistics and characteristic polynomials of cacti graphs and cacti lattices. The method developed is applied to linear cacti, Bethe cacti of any length containing rings of any size, and cyclic cacti of any length and size. It is shown that exact dimer statistics can be done on any cactus lattice.Dedicated to Professor V. Krishnamurthy on the occasion of his 60th birthdayAlfred P. Sloan fellow; Camille and Henry Dreyfus teacher-scholar     

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.     

Computer generation of distance polynomials of graphs

A computer program is developed to compute distance polynomials of graphs containing up to 200 vertices. The code also computes the eigenvalues and the eigenvectors of the distance matrix. It requires as input only the neighborhood information from which the program constructs the distance matrix. The eigenvalues and eigenvectors are computed using the Givens-Householder method while the characteristic polynomials of the distance matrix are constructed using the codes developed by the author before. The newly developed codes are tested out on many graphs containing large numbers of vertices. It is shown that some cyclic isospectral graphs are differentiated by their distance polynomials although distance polynomials themselves are in general not unique structural invariants.     

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.     

Factorization and recursion relations of the matching and characteristic polynomials of periodic polymer networks

Recent developments in the analysis of mathematical structure of the matching and characteristic polynomials of linear and cyclic periodic polymer networks are surveyed, especially on the newly found efficient algorithms and techniques for deriving their recursion relations and factorization expressions. Advantages and disadvantages of these two polynomials for manipulating large networks are compared and discussed with examples. Contrary to the case of singly connected polymer networks, only a few useful mathematical properties are shown to be found for doubly connected polymer networks. Linear and cyclic fence graphs are proposed to be defined instead of the conventional definitions of the so-called Hückel and Möbius ladder graphs, so that simpler and more useful mathematical relations hold for their matching polynomials.     

Imminant polynomials of graphs

Summary The imminant polynomials of the adjacency matrices of graphs are defined. The imminant polynomials of several graphs [linear graphs (L _n ), cyclic graphs (C _n ) and complete graphs (K _n )] are obtained. It is shown that the characteristic polynomials and permanent polynomials become special cases of imminant polynomials. The connection between the Schur-functions and imminant polynomials is outlined.Cammile & Henry Dreyfus Teacher-scholar     

Computer generation of king and color polynomials of graphs and lattices and their applications to statistical mechanics

A computer program is developed in Pascal for the generation of king and color polynomials of graphs. The king polynomial was defined by Motoyama and Hosoya and was shown to be useful in dimer statistics, enumeration of Kekulé structures, etc. We show that the king polynomial of a lattice is the same as the color polynomial of the associated dualist graph, where the color polynomial is defined here as the number of ways of coloring the vertices of a graph with one type of color (say, green) such that two adjacent vertices are not colored with the same color. Applications of these polynomials to exact finite method of lattice statistics are outlined.     

On color polynomials of Fibonacci graphs

A recursion exists among the coefficients of the color polynomials of some of the families of graphs considered in recent work of Balasubramanian and Ramaraj. Such families of graphs have been called Fibonacci graphs. Application to king patterns of lattices is given. The method described here applies only to the so called Fibonacci graphs.     

Method for construction of characteristic polynomials via graph linearization

A new method for construction of characteristic polynomials (CP) of complicated graphs having arbitrary edge and vertex weights has been developed. The method first converts the graph into isospectral linear chains with weighted vertices and edges and then builds up the CP coefficients recursively. Two types of graphs have been used for illustration, viz., (i) graphs that can be linearized by symmetry factorization and (ii) graphs without symmetry which are to be linearized by an algorithm involving walks of unit length. Both types have been illustrated, of which type (i) includes the Schlegel of fullerene fragment C₂₀ and another large graph with many fused rings. © 1997 John Wiley & Sons, Inc. Int J Quant Chem 65 : 199–204, 1997