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

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 enumeration of walks on directed graphs

A vectorized computer code is developed for the enumeration of walks through the matrix power method for directed graphs. Application of this code to several graphs is considered. It is shown that the coefficients in the generating functions for signed graphs are much smaller in magnitude. It is shown that self-avoiding walks on some graphs can be enumerated as a linear combination of walk GFs of directed paths and rooted-directed paths.     

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.     

Molecular graphs as topological objects in space

Stereochemistry deals primarily with distinctions based on rigid geometry, e.g., bond angles and lengths. But some chemical species have molecular graphs (such as knots, catenanes, and nonplanar graphs K₅ and K_3.3) that reside in space in a topologically nontrivial way. For such molecules there is hope of using topological methods to gain chemical information. Viewing a molecular graph as a topological object in space makes it unrealistically flexible; but if one proves that a certain graph is “topologically chiral” or that two graphs are “topological diastereomers,” then one has ruled out interconversion under any physical conditions for which the molecular graph still makes sense. In this paper, we consider several kinds of topological questions one might ask about graphs in space, methology and results available, and specific topological properties of various molecules.     

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

Characteristic polynomials of organic polymers and periodic structures

It is shown that the Frame's method (also, Le Verrier-Faddeev's method) for characteristic polynomials of chemical graphs can be extended to periodic graphs and structures. The finite periodic structures are represented by cyclic structures in the Born-von Kárman boundary condition which leads to complex matrices. In this article we demonstrate that our earlier computer program (based on Frame's method) can be extended to these periodic networks. The characteristic polynomials of several lattices such as polydiacetylenes, one-dimensional triangular, square, and hexagonal lattices are obtained. These polynomials can be obtained with very little computer time using this method.     

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

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.     

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.     

Moments and characteristic polynomials of bipartite Hückel graphs

Moments (u _k ) and coefficients of characteristic polynomials (a _k ) have been evaluated in terms of molecular fragments up tok = 12 for bipartite Hückel graphs. Based on combinatorial analysis, each coefficient can be derived as a combination of binomial factors mapping to the corresponding multi-component graphs. The general formula becomes lengthy as k increases, but can be considerably simplified for a homologous series. This has been illustrated by dealing with the cata-condensed benzenoid hydrocarbons as a corollary where a rather compact set ofa _k has been deduced. On combining the present result with Coulson's formula, one gains insight into the relative stability of isomers in relationship to the energy contribution of fragments classified as stabilized and destabilized species.received by the Publisher 20 September 1989     

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.     

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.     

Dyad algebra and multiplication of graphs. II. Undirected graphs

In paper I abstract vectors |e>, their adjoints <e|, dyads such as |e><e|, and abstract linear operators were related to graphs which are in general directed. With an Hermitian operator one gets equivalence classes of undirected graphs with or without loops and multi-lines. The present paper II gives rules for the multiplication of such graphs based on their underlying dyad algebra. The results may be used in the evaluation of the outcome of successive applications of operators for observables as in the case of the powers of a one-electron Hamiltonian in the method of moments, or in using projection operators, electron density, and the like.     

Details of the reaction graphs for intramolecular isomerizations of the carboranes

From proposed mechanisms for framework reorganizations of the carboranes C₂B _n-2H _n ,n = 5–12, we present reaction graphs in which points or vertices represent individual carborane isomers, while edges or arcs correspond to the various intramolecular rearrangement processes that carry the pair of carbon heteroatoms to different positions within the same polyhedral form. Because they contain both loops and multiple edges, these graphs are actually pseudographs. Loops and multiple edges have chemical significance in several cases. Enantiomeric pairs occur among carborane isomers and among the transition state structures on pathways linking the isomers. For a carborane polyhedral structure withn vertices, each graph hasn(n -1)/2 graph edges. The degree of each graph vertex and the sum of degrees of all graph vertices are independent of the details of the isomerization mechanism. The degree of each vertex is equal to twice the number of rotationally equivalent forms of the corresponding isomer. The total of all vertex degrees is just twice the number of edges orn(n - 1). The degree of each graph vertex is related to the symmetry point group of the structure of the corresponding isomer. Enantiomeric isomer pairs are usually connected in the graph by a single edge and never by more than two edges.