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 using the adjacency matrix power method for perception of symmetry and for isomorphism testing of highly intricate graphs

A modification of the adjacency matrix power method described recently for the perception of symmetry in graphs is introduced, which expands the limits of the method far beyond the realm of chemically interesting graphs. The procedure finds the automorphism partition even for intricate graphs without performing a tree search. The calculation effort increases with the problem size polynomially for all tested cases, including strongly regular graphs, two-level regular graphs, and graphs corresponding to balanced incomplete block designs (BIBD). An equally powerful computer program for testing isomorphism of graphs based on the adjacency matrix power method is introduced.     

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.     

A representation of the McClelland method of graph splitting. Stack graphs

McClelland's rules on graph splitting can be represented using the generalized graph notation. Generalized graphs are edge- and vertex-weighted graphs, which are becoming important to chemical problems. By this the McClelland method of graph splitting has a wider range of applications. “Stack graphs” are constructed from identical “base graphs” by connecting corresponding vertices from one base to another. Their eigenvalues are related to the eigenvalues of the base graph. Two- and even three-layered graphs may be used as a simple model for the inter-ring interaction in a cyclophane.     

Topological analysis of some special classes of graphs. II. steps,ladders, cylinders

A general strategy is proposed for generating the eigenvectors and the eigenvalues of some special classes of graphs from the well-known chemical graphs such as lines and cycles which are isomorphic to the hydrogen-suppressed linear and cyclic polyenes. This method is applied to step graphs, ladders, cylinders, etc. Net sign analyses are then performed for all these special classes of graphs.     

Wiener, hyper-Wiener, detour and hyper-detour indices of bridge and chain graphs

Given a collection of connected graphs one may build bridge and chain graphs out of them. In this paper it is shown how the Wiener, hyper-Wiener, detour and hyper-detour indices for bridge and chain graphs are determined from the respective indices of the individual graphs. The results obtained are illustrated by some examples.     

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.     

Functional groups expressed as graphs extracted from the Laplacian of the electron density

The valence charge concentration shell, as determined by the Laplacian of the electron density, is used as a source of quantum topological graphs, called L‐graphs. A considerable number of such graphs are extracted from the ab initio wave functions of 31 molecules calculated at the B3LYP/6‐311+G(2d,p)//B3LYP/6‐311+G(2d,p) level, covering common functional groups in organic chemistry. We show how L‐graphs can be constructed from a largely transferable subgraph called atomic L‐graph. We investigate the topological stability of the L‐graphs as a function of the basis set. Reliable and consistent atomic L‐graphs are only obtained with basis sets of triple‐zeta quality or higher. The recurrence of invariant motifs or subgraphs in the L‐graphs enables the isolation of 16 atomic L‐graphs. © 2003 Wiley Periodicals, Inc. Int J Quantum Chem, 2003     

Graphs of unbranched hexagonal systems with equal values of the wiener index and different numbers of rings

Graphs of unbranched hexagonal systems consist of hexagonal rings connected with each other. Molecular graphs of unbranched polycyclic aromatic hydrocarbons serve as an example of graphs of this class. The Wiener index (or the Wiener number) of a graph is defined as the sum of distances between all pairs of its vertices. Necessary conditions for the existence of graphs with different numbers of hexagonal rings and equal values of the Wiener index are formulated, and examples of such graphs are presented.     

Computer generation of edge groups and edge colorings of graphs

A computer code and nonnumerical algorithm are developed to construct the edge group of a graph and to enumerate the edge colorings of graphs of chemical interest. The edge colorings of graphs have many applications in nuclear magnetic resonance (NMR), multiple quantum NMR, enumeration of structural isomers of unsaturated organic compounds, and in the construction of configurational integral expansion series in statistical mechanics. The code developed is applied to many NMR graphs, complete graphs containing up to 10 vertices, and the Petersen graph.     

Combinatorial properties of graphs and groups of physico-chemical interest

Combinatorial properties of graphs and groups of physico-chemical interest are described. A type of mathematical modeling is applied which involves "translating" algebraic expressions into graphs. The idea is applied to both graph theory and group theory. The former topic includes objects of importance in physics and chemistry such as trees, polyomino graphs, king boards, etc. Our study along these lines emphasizes nonadjacency relations, graph-generation, quasicrystals, continued fractions, fractals, and general ordering schemes of graphs. The second part of the paper considers certain colored graphs as models of several group-theoretical concepts including coset representations of groups, subduction of groups, character tables, and mark tables which are essential to the understanding of recent developments of combinatorial enumeration in chemistry.     

Graphical shapes: Seeing graphs of chemical curves and molecular surfaces

Interior seeing graphs of Jordan curves and two-dimensional closed surfaces are proposed for the characterisation or the shapes of chemical curves and surfaces. Some of the relevant properties of seeing graphs, in particular, of seeing trees, are described. The proposed applications of seeing graphs provide a molecular shape characterization by converting the continuum problem of a molecular contour surface, for example, Mat of an isodensity contour of molecular electronic charge distribution, into a discrete problem of a graph. The dependence of seeing graphs on be charge density contour value, a continuous parameter, is analysed. The family of seeing graphs occurring; within the chemically accessible range of charge density contour values is proposed for a computer-based analysis of molecular similarity. The general method is illustrated with the example of a detailed study on the family of seeing graphs of the electronic charge density of the ethene molecule.     

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     

Applications of caterpillar trees in chemistry and physics

The relations of caterpillar trees (which are also known as Gutman trees and benzenoid trees) to other mathematical objects such as polyhex graphs, Clar graphs, king polyominos, rook boards and Young diagrams are discussed. Potential uses of such trees in data reduction, computational graph theory, and in the ordering of graphs are considered. Combinatorial and physical properties of benzenoid hydrocarbons can be studied via related caterpillars. It thus becomes possible to study the properties of large graphs such as benzenoid (i.e. polyhex) graphs in terms of much smaller tree graphs. Generation of the cyclic structures of wreath and generalized wreath product groups through the use of caterpillar trees is illustrated.     

Note on the topological information content of simple graphs

It is shown that simple graphs gave equal topological information content if their automorphism groups are isomorphic. Further, if the automorphism groups of two graphs are represented by wreath products of which the inner groups are isomorphic, then the two graphs possess equal topological information content. Three graphs which correspond to organic molecules illustrate this finding.Dedicated to Professor Dr.Karl Schlögl on the occasion of his 60th birthday.     

Degeneracy of some matrix graph invariants

New matrices associated with graphs and induced global and local topological indices of molecular graphs were proposed recently by Diudea, Minailiuc and Balaban. These matrices in canonical form are matrix graph invariants. A combined degeneracy of such invariants is considered. For every case of degeneracy corresponding graphs are presented.     

Large-scale analysis of structural branching measures

Structural branching of graphs has been investigated extensively. Yet, no method/model has yet been developed which captures all aspects of branching meaningfully. Another shortcoming of nearly all related work in this area is the fact that only small sets of example graphs have been used to perform those studies. Instead, we investigate structural branching of graphs statistically by using large sets of exhaustively generated graphs. Our findings explain some of the limits of existing branching measures as well as the search for novel branching measures by using correlation analysis.     

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