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.     

On the z-counting polynomial for edge-weighted graphs

The construction of the Z-counting polynomial for edge-weighted graphs is discussed.Dedicated to Professor Haruo Hosoya (Tokyo) on the occasion of his 55th birthday for enriching chemical graph theory with the elegant concept of the Z-counting polynomial.     

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

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.     

Planar polycyclic graphs and their Tutte polynomials

We consider several classes of planar polycyclic graphs and derive recurrences satisfied by their Tutte polynomials. The recurrences are then solved by computing the corresponding generating functions. As a consequence, we obtain values of several chemically and combinatorially interesting enumerative invariants of considered graphs. Some of them can be expressed in terms of values of Chebyshev polynomials of the second kind.     

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.     

On the characteristic polynomials of spirographs and related graphs

General recursive techniques are used to determine recurrence relations for the characteristic polynomials of graphs associated with various ring compounds.     

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.     

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.     

Characteristic polynomials of large graphs. On alternate form of characteristic polynomial [1]

A recursion exists between the absolute magnitudes of the coefficients of the characteristic polynomials of certain families of cyclic and acyclic graphs which makes their computation quite easy for very large graphs using a pencil-and-a-paper approach. Structural requirements are given for such families of graphs which are of interest to the problem of recognition defined in [1].     

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.     

Homomorphism polynomials of chemical graphs

We say that a graphG ishomomorphic to a graphH if there is a mappingp from the vertices of G onto the vertices ofH such thatp(u) andp() are adjacent inH wheneveru and are adjacent in G. Thehomomorphism polynomial of a graphG is a polynomial in two variables that counts the number of homomorphisms ofG onto the complete graph of each order. This polynomial can be computed recursively in an analog to the chromatic polynomial. In this paper, we present some results regarding the homomorphism polynomials of the graphs of chemical compounds — in particular, alkane isomers. The coefficients of the homomorphism polynomial can be used to predict the rankings of compounds with respect to several chemical properties. Our results seem to refine those obtained by Randi et al. from path lengths.     

Wiener polynomials of some chemically interesting graphs

The chemist Harold Wiener found ??(G), the sum of distances between all pairs of vertices in a connected graph G, to be useful as a predictor of certain physical and chemical properties. The q‐analogue of ??, called the Wiener polynomial ??(G; q), is also useful, but it has few existing useful formulas. We will evaluate ??(G; q) for certain graphs G of chemical interest. © 2004 Wiley Periodicals, Inc. Int J Quantum Chem, 2004     

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.     

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.     

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.     

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