Structural covariance of graphs

Algebraic structures including multiple rank tensors, linear and non-linear operators are related to and represented with various types of graphs. Special emphasis is placed on linear operators e.g. on the Hibert space. A different graph represents the same operator depending on the basis frame used, in general non-orthonormal. All such graphs are shown to belong in one equivalence class and are termed structurally covariant. Crucial indices related to eigenvalues but invariant under any basis frame changes including non-orthonormal ones provide one way to characterize each class. A set of rules are given that allow one to find the graphs structurally covarinat with a given one and/or to deduce the class indices directly by simple pictorial manipulations on a graph. Applications in various fields including the quantum theory of molecules and reactions are indicated.     

Chemical graphs

In order to find the centre of an acyclic connected graph (of a tree), vertices of degree one (endpoints) are removed stepwise. The numbers _i of vertices thus removed at each step form a digit sequenceS (pruning sequence) which reflects the branching of the tree. The sum of squares of digits in the sequenceS affords a new topologicalcentric index B = _{i i} ² for the branching of trees. Comparisons with other topological indices are presented evidencing thatB induces an ordering of isomeric trees distinct from those induced by all other indices devised so far, becauseB emphasizes equally branches of similar length.It is shown that Rouvray's indexIis equivalent to Wiener's indexw, and that the Gordon-Scantlebury indexN ₂ and Gutmanet al.'s indexM ₁ belong to the same family, calledquadratic indices, and induce the same ordering.Since all topological indices vary both with the branching and the number of vertices in the tree, four new indices are devised fromB andM ₁ to account only (or mainly) for the branching, by normalization (imposing a lower bound equal to zero for chain-graphs, i.e.n-alkanes) or binormalization (same lower bound, and upper bound equal to one for star-graphs). Normalized and binormalized centric (C, C) and quadratic indices (Q, Q) are presented for the lower alkanes. From the five new topological indices, the centric indices (B, C, C) are limited to trees, but the quadratic indices (Q, Q) apply to any graph. Binormalized indices (C,Q) express the topological shape of the graph.     

Fast construction of assembly trees for molecular graphs

A number of modeling and simulation algorithms using internal coordinates rely on hierarchical representations of molecular systems. Given the potentially complex topologies of molecular systems, though, automatically generating such hierarchical decompositions may be difficult. In this article, we present a fast general algorithm for the complete construction of a hierarchical representation of a molecular system. This two-step algorithm treats the input molecular system as a graph in which vertices represent atoms or pseudo-atoms, and edges represent covalent bonds. The first step contracts all cycles in the input graph. The second step builds an assembly tree from the reduced graph. We analyze the complexity of this algorithm and show that the first step is linear in the number of edges in the input graph, whereas the second one is linear in the number of edges in the graph without cycles, but dependent on the branching factor of the molecular graph. We demonstrate the performance of our algorithm on a set of specifically tailored difficult cases as well as on a large subset of molecular graphs extracted from the protein data bank. In particular, we experimentally show that both steps behave linearly in the number of edges in the input graph (the branching factor is fixed for the second step). Finally, we demonstrate an application of our hierarchy construction algorithm to adaptive torsion-angle molecular mechanics.     

Reaction graphs and a construction of reaction networks

Summary A general definition of reaction graphs is presented. For a pair of isomeric molecular graphs and , related by a chemical transformation , the reaction graph is determined using a maximal common subgraph defined for vertex mapping . A binary operation defined for graphs constructed over the same vertex set enables us to decompose the reaction graph into the sum of prototype reaction graphs. A decomposition of an overall reaction graph can be advantageously used for the construction of a reaction network. An oriented path in this network beginning at and ending at corresponds to a breakdown of the transformation into a sequence of intermediates.     

Effect of molecular structure of curing agents on cyclic creep in highly cross-linked epoxy polymers

Ratcheting behavior of highly–cross-linked epoxy polymers was investigated considering the effect of molecular structure of curing agents by molecular dynamics simulations. Cyclic loading–unloading simulations at two different frequencies were conducted using atomistic models for epoxies cured by aliphatic and aromatic curing agents, triethylenetetramine (TETA) and diethyltoluenediamine (DETDA), respectively. Different ratcheting strain evolutions, dihedral angle stress accumulations, and stiffness variations were observed during the cyclic deformation simulations depending on the molecular structure of curing agents. The epoxy cured by DETDA exhibited a more rapid increase of ratcheting strain and a decrease of the stiffness toward the loading direction. Structural analyses were carried out by observing the orientation order parameter of the monomers, radius of gyration, and free volume evolution to understand the ratcheting strain behaviors and stiffness variations at atomistic scale. The structural analyses revealed that irreversible dihedral angle transitions near the benzene ring of the curing agent DETDA were responsible for low ratcheting resistance and stiffness degradation during the cyclic deformations. Whereas, the aliphatic curing agent TETA, which does not exhibit any stress possession by the irreversible dihedral angle change, was revealed to be advantageous for the ratcheting resistance and stiffness variation of the epoxy polymers.     

Minimal energy of unicyclic graphs of a given diameter

The energy of a graph is defined as the sum of the absolute values of all the eigenvalues of the graph. For a given positive integer d with , we characterize the graphs with minimal energy in the class of unicyclic graphs with n vertices and a given diameter d.      

Characteristic polynomials of chemical graphs via symmetric function theory

The characteristic polynomial corresponding to the adjacency matrix of a graph is constructed by using the traces of the powers of the adjacency matrix to calculate the coefficients of the characteristic polynomial via Newton's identities connecting the power sum symmetric functions and the elementary symmetric functions of the eigenvalues. It is shown that Frame's method, very recently employed by Balasubramanian, is nothing but symmetric functions and Newton's identities.     

Construction of characteristic polynomial of reciprocal graphs from the number of pendant vertices

A method for construction of the characteristic polynomial (CP) coefficients of the three classes of reciprocal graphs, viz., L_n + n(p), C_n + n(p), and K_1,n?1 + n(p), has been developed that requires only the value of n. The working formulas have been expressed in matrix product form, computer programs for which can easily be developed. © 2004 Wiley Periodicals, Inc. Int J Quantum Chem, 2005     

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     

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.     

Calibration graphs in isotope dilution mass spectrometry

Isotope-based quantitation is routinely employed in chemical measurements. Whereas most analysts seek for methods with linear theoretical response functions, a unique feature that distinguishes isotope dilution from many other analytical methods is the inherent possibility for a nonlinear theoretical response curve. Most implementations of isotope dilution calibration today either eliminate the nonlinearity by employing internal standards with markedly different molecular weight or they employ empirical polynomial fits. Here we show that the exact curvature of any isotope dilution curve can be obtained from three-parameter rational function, y = f(q) = (a₀ + a₁q)/(1 + a₂q), known as the Padé[1,1] approximant. The use of this function allows eliminating an unnecessary source of error in isotope dilution analysis when faced with nonlinear calibration curves. In addition, fitting with Padé model can be done using linear least squares.     

Core electrons and hydrogen atoms in chemical graph theory

General and complete graphs have recently been used to free chemical graph theory, and especially molecular connectivity theory, from spurious concepts, which belonged to quantum chemistry with no direct counterpart in graph theory. Both types of graph concepts allow the encoding of multiple bonds, non-bonding electrons, and core electrons. Furthermore, they allow the encoding of the bonded hydrogen atoms, which are normally suppressed in chemical graphs. This suppression could sometimes have nasty consequences, like the impossibility to differentiate between compounds, whose hydrogen-suppressed chemical graphs are completely equivalent, like for the CH₂F₂ and BHF₂ compounds. At the computational level the new graph concepts do not introduce any dramatic changes relatively to previous QSPR/QSAR studies. These concepts can nevertheless help in encoding the many electronic features of a molecule, achieving, as a bonus, an improved quality of the modeled properties, as it is here exemplified with a set of properties of different classes of compounds.     

Resistance distance in graphs and random walks

We study the resistance distance on connected undirected graphs, linking this concept to the fruitful area of random walks on graphs. We provide two short proofs of a general lower bound for the resistance, or Kirchhoff index, of graphs on N vertices, as well as an upper bound and a general formula to compute it exactly, whose complexity is that of inverting an N×N matrix. We argue that the formulas for the resistance in the case of the Platonic solids can be generalized to all distance‐transitive graphs. © 2001 John Wiley & Sons, Inc. Int J Quant Chem 81: 29–33, 2001     

Metric properties of the functions of distances between molecular graphs

The metric properties of several functions of distances between the molecular (marked) graphs, depending on the size of the largest common subgraphs, are discussed. Recommendations are given on how to use these functions in investigations of samples of chemical compounds.     

Two new graph-theoretical methods for generation of eigenvectors of chemical graphs

Two new graph-theoretical methods, (A) and (B), have been devised for generation of eigenvectors of weighted and unweighted chemical graphs. Both the methods show that not only eigenvalues but also eigenvectors have full combinatorial (graph-theoretical) content. Method (A) expresses eigenvector components in terms of Ulam’s subgraphs of the graph. For degenerate eigenvalues this method fails, but still the expressions developed yield a method for predicting the multiplicities of degenerate eigenvalues in the graph-spectrum. Some well-known results about complete graphs (K _n) and annulenes (C _n ), viz. (i)K _n has an eigenvalue −1 with (n−1)-fold degeneracy and (ii) C _n cannot show more than two-fold degeneracy, can be proved very easily by employing the eigenvector expression developed in method (A). Method (B) expresses the eigenvectors as analytic functions of the eigenvalues using the cofactor approach. This method also fails in the case of degenerate eigenvalues but can be utilised successfully in case of accidental degeneracies by using symmetry-adapted linear combinations. Method (B) has been applied to analyse the trend in charge-transfer absorption maxima of the some molecular complexes and the hyperconjugative HMO parameters of the methyl group have been obtained from this trend.     

A graph-theoretical method for stepwise factorisation of symmetric graphs for simultaneous determination of eigenvectors and eigenvalues

A simple pictorial algorithm for factorisation of symmetric chemical graphs (weighted and unweighted) leading to simultaneous determination of their eigenvalues and eigenvectors has been devised. The method does not require group-theoretical techniques (viz. identification of the point group of the species under study, formation of symmetryadopted linear combinations using character tables etc.). It requires consideration of only one symmetry element, e.g., a reflection plane and is based on elementary row and column operations which keep the secular determinant of the adjacency matrix unchanged (except possibly for a multiplicative constant).     

Graph theoretical procedure for obtaining analytical expressions of eigenspectra of linear chains and cycles with alternant vertex weights and same edge weight: Application to some complicated graphs

A graph theoretical procedure for obtaining eigenvalues of linear chains and cycles having alternant vertex weights (h₁, h₂, h₁, h₂, h₁, h₂, …) and the same edge weight (k) have been developed. The eigenvalues of some complicated graphs, such as graphs of linear polyacenes, methylene‐substituted linear polyacenes and cylindrical polyacene strips, stack graphs, and reciprocal graphs have been shown to be generated in closed analytical forms by this procedure. Many such graphs represent chemically important molecules or radicals. © 2005 Wiley Periodicals, Inc. Int J Quantum Chem, 2005