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 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 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.     

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.     

Generalized Wheland polynomial for large graphs

We report the generalized Wheland polynomial for acyclic graphs depicting polyenes havingn = 10 carbon atoms. We consider the problem of deriving generalized Wheland polynomials for larger chains by recursion. The recursion Wh(n + l;x) =, Wh(n; x) + (1 –x)Wh(n – 1;x) allows one to find the next larger generalized Wheland polynomial for a chain having an even number of vertices by knowing generalized Wheland polynomials of chains having fewer vertices. The recursion, however, does not allow one to predict the generalized Wheland polynomial for a chain having an odd number of vertices from smaller chains! Here we report a procedure which allows one to derive the generalized Wheland polynomial for a chain having an odd number of vertices. This is achieved by combining the coefficients for rings having the same number of vertices. The generalized Wheland polynomials for odd rings are simply related to the generalized Wheland polynomials for smaller chains and can be derived from the information on smaller chains. This makes it possible to extend the recursion for generalized Wheland polynomials for arbitrarily largen.     

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     

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 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.     

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.     

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.     

Comments on the characteristic polynomial of a graph

Several unique advantages of the Le Verrier–Fadeev–Frame method for the characteristic polynomials of graphs over the method proposed by Zivkovi? recently based on the Givens–Householder method are described. It is shown that the Givens–Householder method proposed by Zivkovi?, by itself fails for directed graphs, signed graphs, and complex nonhermetian graphs requiring extensive modifications to the Householder algorithm through the double + random shift QR procedure requiring more computations than claimed. Furthermore, the QR procedure does not always converge and requires random shifts. To the contrary, it is shown that the Le Verrier–Fadeev–Frame method does not require any such modifications or random shifts and takes less total CPU times when both algorithms are run using vector processors. Hence it is demonstrated that the Le Verrier–Frame algorithm is efficient and superior in its universal and direct applicability to all graphs requiring no further modifications (directed, signed, and complex).     

On the centrality of vertices of molecular graphs

For acyclic systems the center of a graph has been known to be either a single vertex of two adjacent vertices, that is, an edge. It has not been quite clear how to extend the concept of graph center to polycyclic systems. Several approaches to the graph center of molecular graphs of polycyclic graphs have been proposed in the literature. In most cases alternative approaches, however, while being apparently equally plausible, gave the same results for many molecules, but occasionally they differ in their characterization of molecular center. In order to reduce the number of vertices that would qualify as forming the center of the graph, a hierarchy of rules have been considered in the search for graph centers. We reconsidered the problem of “the center of a graph” by using a novel concept of graph theory, the vertex “weights,” defined by counting the number of pairs of vertices at the same distance from the vertex considered. This approach gives often the same results for graph centers of acyclic graphs as the standard definition of graph center based on vertex eccentricities. However, in some cases when two nonequivalent vertices have been found as graph center, the novel approach can discriminate between the two. The same approach applies to cyclic graphs without additional rules to locate the vertex or vertices forming the center of polycyclic graphs, vertices referred to as central vertices of a graph. In addition, the novel vertex “weights,” in the case of acyclic, cyclic, and polycyclic graphs can be interpreted as vertex centralities, a measure for how close or distant vertices are from the center or central vertices of the graph. Besides illustrating the centralities of a number of smaller polycyclic graphs, we also report on several acyclic graphs showing the same centrality values of their vertices. © 2013 Wiley Periodicals, Inc.     

Theory and computational applications of Fibonacci graphs

The concept of Fibonacci graphs introduced and developed by this author is critically reviewed. The concept has been shown to provide an easypencil-and-paper method of calculating characteristic, matching, counting, sextet, rook, color and king polynomials of graphs of quite large size with limited connectivities. For example, the coefficients of the matching polynomial of 18-annuleno—18-annulene can be obtainedby hand using the definition of Fibonacci graphs. They are (in absolute magnitudes): 1, 35, 557, 5337, 34 361, 157 081, 525 296, 1304 426, 2 416 571, 3 327 037, 3 362 528, 2 440 842, 1 229 614, 407 814, 81936, 8652, 361, 3. The theory of Fibonacci graphs is reviewed in an easy and detailed language. The theory leads to modulation of the polynomial of a graph with the polynomial of a path.Dedicated to Professor R. Bruce King for his enthusiastic promotion and contributions to Mathematical Chemistry.     

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.     

An algebraic approach to the study of the titration curves of weak acids and their mixtures

It is shown that the titration curves of weak acids and their mixtures which have rational mole-fractions of the components can be transformed into polynomials. These protonation polynomials are called normal or abnormal according to whether their coefficients do or do not satisfy certain inequalities derived from statistical considerations. The normality of a second-degree polynomial is shown to be a characteristic equivalent to the reality of its zeros. Protonation polynomials with real zeros are shown to be normal, but the converse of this statement is not necessarily true. The titration curve of a polyfunctional acid is identical with that of an equimolar mixture of monofunctional acids if and only if the protonation polynomial has real zeros. A method for determining the functionality of an acid from its titration curve by using protonation polynomials is outlined.     

Isorpectral multitrees

We examined trees with one multiple edge (of multiplicityk) and report all isospectral graphs found when the number of vertices was n < 9. Tile search for isospectrul multitrees was carried out systematically by constructing the characteristic polynomials of all trees having one weighted edge. For all multitrees havingn < 7 vertices, we tabulated the coefficients of the characteristic polynomial. We restricted the analysis to trees with Me maximal valencyd = 4. The number of graphs considered exceeds 300. The smallest pair of isospectral multitrees (i.e. trees with a multiple edge) hasn = 6 vertices, There is a pair of trees whenn = 7, three pairs whenn = 8, and five pads whenn = 9. In all cases, whenk = I is assumed, isospectral multitrees reduce to the same tree. Whenk = 0 is assume(], isospectral trees produce either the same disconnected graph, or an isospectral forest.Dedicated to Basil E. Gillam, Professor emeritus of the Department of Mathematics and Computer Science at Drake University.Reported in part at the 1986 International Congress of Mathematicians, Berkeley, California, USA.Operated for the U.S. Department of Energy by the Iowa State University under Contract No. W-7405-Eng-82. This work was supported in part by the Office of R.S. Hansen, Director.     

Computer program for finding all possible cycles in graphs

A new approach is presented for identifying all possible cycles in graphs. Input data are the total numbers of vertices and edges, as well as the vertex adjacencies using arbitrary vertex numbering. A homeomorphically reduced graph (HRG) is constructed by ignoring vertices of degree less than three. The algorithm is based on successive generation of possible edge-combinations in the HRG. If a combination yields a cycle, it is either printed or stored and then finally printed in a list of all possible cycles arranged in the order of increasing ring size. A unique numbering of the cycle is used. The computer program is listed and exemplified. Computing times are given.     

Computer generation of acyclic graphs based on local vertex invariants and topological indices. Derived canonical labelling and coding of trees and alkanes

A new procedure (GENLOIS) is presented for generating trees or certain classes of trees such as 4-trees (graphs representing alkanes), identity trees, homeomorphical irreducible trees, rooted trees, trees labelled on a certain vertex (primary, secondary, tertiary, etc.). The present method differs from previous procedures by differentiating among the vertices of a given parent graph by means of local vertex invariants (LOVIs). New graphs are efficiently generated by adding points and/or edges only to non-equivalent vertices of the parent graph. Redundant generation of graphs is minimized and checked by means of highly discriminating, recently devised topological indices based either on LOVIs or on the information content of LOVIs. All trees onN + 1 (N + 1 < 17) points could thus be generated from the complete set of trees onN points. A unique cooperative labelling for trees results as a consequence of the generation scheme. This labelling can be translated into a code for which canonical rules were recently stated by A.T. Balaban. This coding appears to be one of the best procedures for encoding, retrieving or ordering the molecular structure of trees (or alkanes).Dedicated to Professor Alexandru T. Balaban on the occasion of his 60th anniversary.     

Subgraphs of pair vertices

Subgraphs obtained by applying several fragmentation criteria are investigated. Two well known criteria (Szeged and Cluj), and two new others are defined and characterized. An example is given for the discussed procedures. The matrix and polynomial representations of vertices composing each type of subgraphs were also given. Analytical formulas for the polynomials of several classes of graphs are derived. The newly introduced subgraphs/fragments, called MaxF and CMaxF, appear to have interesting properties, which are demonstrated.