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.     

Spectra of chemical trees

A method is developed for obtaining the spectra of trees of NMR and chemical interests. The characteristic polynomials of branched trees can be obtained in terms of the characteristic polynomials of unbranched trees and branches by pruning the tree at the joints. The unbranched trees can also be broken down further till we obtain a tree containing just two vertices. This effectively reduces the order of the secular determinant of the tree we started with to determinants of orders atmost equal to the number of vertices in the branch containing the largest number of vertices. An illustrative example of a NMR graph is given for which the 22 × 22 secular determinant is reduced to determinants of orders atmost 4 × 4 in just the second step of the algorithm. The tree pruning algorithm can be applied even to trees with no symmetry elements and such a factoring can be achieved. Methods developed here can be elegantly used to find if two trees are cospectral and to construct cospectral trees.     

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

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.     

On Wiener‐type polynomials of thorn graphs

We derive the expressions of the ordinary, the vertex‐weighted and the doubly vertex‐weighted Wiener polynomials of a type of thorn graph, for which the number of pendant edges attached to any vertex of the underlying parent graph is a linear function of its degree. We also define variable vertex‐weighted Wiener polynomials and calculate them for the same type of thorn graphs. Copyright © 2009 John Wiley & Sons, Ltd.     

The graph center concept for polycyclic graphs

While the concept of the graph center is unambiguous (and quite old) in the case of acyclic graphs, an attempt has been made recently to extend the concept to polycyclic structures using the distance matrix of a graph as the basis. In this work we continue exploring such generalizations considering in addition to the distance matrix, self-avoiding walks or paths as graph invariants of potential interest for discriminating distinctive vertex environments in a graph of polycyclic structures. A hierachy of criteria is suggested that offers a systematic approach to the vertex discrimination and eventually establishes in most cases the graph center as a single vertex, a single bond (edge), or a single group of equivalent vertices. Some applications and the significance of the concept of the graph center are 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.     

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.     

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.     

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     

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.     

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     

Fibonacci relations. On the computation of some counting polynomials of very large graphs

A definition of a set of Fibonacci graphs is introduced which allows construction of several counting polynomials of very large graphs quite easily using a pencil-and-a-paper approach. These polynomials include matching, sextet, independence, Aihara and Hosoya polynomials. Certain combinatorial properties of Kekulé counts of benzenoid hydrocarbons are given. A relation to a new topological function that counts the cardinality of graph topology [23] is given.Dedicated to Professor Oskar E. Polansky for his enthusiastic support, participation and promotion of chemical graph theory.     

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.     

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.     

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.     

On reciprocal reverse Wiener index

We report some properties, especially bounds for the reciprocal reverse Wiener index of a connected (molecular) graph. We find that the reciprocal reverse Wiener index possesses the minimum values for the complete graph in the class of n-vertex connected graphs and for the star in the class of n-vertex trees, and the maximum values for the complete graph with one edge deleted in the class of n-vertex connected graphs and for the tree obtained by attaching a pendant vertex to a pendant vertex of the star on n − 1 vertices in the class of n-vertex trees. These results are compared with those obtained for the ordinary Wiener index.     

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.     

Graph generators

We consider the construction of highly symmetrical vertex transitive graphs. Some such graphs represent the degenerate rearrangements in which a molecule or an ion is formed by breaking and making bonds so that the final and the initial skeleton is identical. The approach is closely related to Cayley's graphs for selected groups. We restrict the choice of generators to symmetric matrices. Successive multiplications of such matrices generate other permutation matrices of the same dimension, each new matrix representing a new vertex for a transitive graph under the construction. In particular we restrict our discussion to matrices of dimension 3 and 4 and proceed to construct systematically all transitive graphs using 4 × 4 symmetric matrices as generators.