Comment on ‘Topological Analysis of the Eigenvalues of the Adjacency Matrices in Graph Theory: A Difficulty with the Concept of Internal Connectivity’

Net signs of edge-signed graphs obtained for different choices of degenerate eigenvectors of an adjacency matrix are shown to become equal with a simple weighting procedure. However, in a few cases, this simple procedure is found to yield orderings of the eigenvectors based on the weighted net signs which are different from the orderings based on the eigenvalues.     

On valency based topological properties of the starphene St[n,m,l] and fenestrene F[n,m]

In theoretical chemistry the quantitative parameters which are used to describe the atomic topology of graphs are termed as topological indices. Through these topological indices many physical and chemical characteristics such as melting point, entropy, energy generation and vaporisation enthalpy of chemical compounds can be predicted. The theory of graphs has a significant use in measuring the relationship of certain associated graphs with various topological indices. In this paper, we compute novel topological indices based on eV- and ve-degrees for starphene $\mathit{St}[n,m,l]$ and fenestrene $F[n,m]$. A Maple-based algorithm is proposed for the calculation of ve and eV-degree based topological indices from the graph adjacency matrix.     

On eigenvalues and eigenvectors of graphs

It is known that there exists an equivalence relation between the adjacency matrix of graph theory and the Hückel matrix of Hückel molecular orbital theory. This paper presents some useful methods which allow us to systematically find eigenvalues and eigenvectors of various classes of graphs without calculating characteristic polynomials. Results obtained from this study give insight into the topological studies of molecular orbitals.Dedicated to Professor Frank Harary on the occasion of his 70th birthday.     

Generalized graphs and the Sinanoğlu graphical rules

A comparison of Sinano?lu's VIF (Ref. 1) and generalized graph is presented. Generalized graphs have vertex and edge weights. An abridged history of generalized graphs in theoretical chemistry is given. VIF 's are generalized graphs and therefore have adjacency matrices. The “graphical” rules of Sinano?lu can be represented by congruent transformations on the adjacency matrix. Thus the method of Sinano?lu is incorporated into the broad scheme of graph spectral theory. If the signature of a graph is defined as the collection of the number of positive, zero, and negative eigenvalues of the graph's adjacency matrix, then it is identical to the all-important {n₊, n₀, n_?}, the {number of positive, zero, and negative loops of a reduced graph} or the {number of bonding, nonbonding, and antibonding MO s}. A special case of the Sinano?lu rules is the “multiplication of a vertex” by (?1). In matrix language, this multiplication is an orthogonal transformation of the adjacency matrix. Thus, one can multiply any vertex of a generalized graph by ?1 without changing its eigenvalues.     

Chemical signed graph theory

Chemical signed graph theory is presented. Each topological orbital of an N-vertex molecular graph is represented by a vertex-signed graph (VSG ) that is generated by assigning a sign, either plus or minus, to the vertices without solving the secular matrix equation. The bonding capacity of each VSG is represented by its corresponding edge-signed graph (ESG ) and is quantified by the net sign of the ESG . The resulting 2^N–1 configurations of VSG s can be divided into several groups according to the net signs of the corresponding ESG s. Summation of an appropriate set of degenerate VSG s is found to yield the conventional, canonical molecular orbitals. The distribution of the number of VSG s with respect to the net sign is found to be binomial, which can be related to bond percolation in statistical physics. © 1994 John Wiley & Sons, Inc.     

Pairing theorem of graph eigenvalues: Its new proof and a generalization

Each undirected graph has its own adjacency matrix, which is real and symmetric. The negative of the adjacency matrix, also real and symmetric, is a well-defined mathematically elementary concept. By this negative adjacency matrix, the negative of a graph can be defined. Then an orthogonal transformation can be readily found that transforms a negative of an alternant graph to that alternant graph: (?G) → G. Since the procedure does not involve the edge weights, the pairing theorem holds true for all edge-weighted alternant graphs, including the usual “standard” graphs.     

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.     

Eigenvector and eigenvalues of some special graphs. IV. Multilevel circulants

A multilevel circulant is defined as a graph whose adjacency matrix has a certain block decomposition into circulant matrices. A general algebraic method for finding the eigenvectors and the eigenvalues of multilevel circulants is given. Several classes of graphs, including regular polyhedra, suns, and cylinders can be analyzed using this scheme.     

GrInvIn in a nutshell

GrInvIn (Graph Invariant Investigator) is a software framework for teaching graph theory and for research in graph theory and graph theoretic chemistry. It enables users to construct graphs, compute invariants (e.g. topological indices in chemistry) and investigate relations between these concepts. The design of GrInvIn emphasizes easy usage and makes use of software engineering techniques that enable the user to easily extend the system (e.g. by adding new topological indices to investigate).     

On the evaluation of the characteristic polynomial of a chemical graph

The evaluation of the characteristic polynomial of a chemical graph is considered. It is shown that the operation count of the Le Verrier–Faddeev–Frame method, which is presently considered to be the most efficient method for the calculation of the characteristic polynomial, is of the order n⁴. Here n is the order of the adjacency matrix A or equivalently, the number of vertices in the graph G. Two new algorithms are described which both have the operation count of the order n³. These algorithms are stable, fast, and efficient. A related problem of finding a characteristic polynomial from the known eigenvalues λ_i of the adjacency matrix is also considered. An algorithm is described which requires only n(n ? 1)/2 operations for the solution of this problem.     

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.     

Splitting of n-fold rotationally symmetric graphs

R. A. Davidson's rules for splitting an n-fold rotationally symmetric graph can be derived from a unitary transformation on the adjacency matrix. The McClelland and D'Amato rules are special cases with n = 2 and n = 3, respectively.     

On the geometric–arithmetic index by decompositions-CMMSE

The concept of geometric–arithmetic index was introduced in the chemical graph theory recently, but it has shown to be useful. There are many papers studying different kinds of indices (as Wiener, hyper–Wiener, detour, hyper–detour, Szeged, edge–Szeged, PI, vertex–PI and eccentric connectivity indices) under particular cases of decompositions. The main aim of this paper is to show that the computation of the geometric-arithmetic index of a graph G is essentially reduced to the computation of the geometric-arithmetic indices of the so-called primary subgraphs obtained by a general decomposition of G. Furthermore, using these results, we obtain formulas for the geometric-arithmetic indices of bridge graphs and other classes of graphs, like bouquet of graphs and circle graphs. These results are applied to the computation of the geometric-arithmetic index of Spiro chain of hexagons, polyphenylenes and polyethene.     

Phased graphs and graph energies

We define a phased graph G to yield an adjacency matrix A(G) having general magnitude-1 values in the same locations as the usual unphased case, but subject to the restriction that A be Hermitian. Some characteristics of such phased graphs and their eigenspectra are contemplated and to some extent described. Different graph energies are defined as suitable sums over adjacency-matrix eigenvalues, with ??occupation-number?? coefficients ${\in \{0,1, 2\}}$ .     

Highly discriminating distance-based topological index

A new topological indexJ (based on distance sumss_i as graph invariants) is proposed. For unsaturated or aromatic compounds, fractional bond orders are used in calculatings_i. The degeneracy ofJ is lowest among all single topological indices described so far. The asymptotic behaviour ofJ is discussed, e.g. whenn → ∞ in C_nH_{2n = 2},Jar π for linear alkanes, andJ → ∞ for highly branched ones.     

S5 graphs as model systems for icosahedral Jahn–Teller problems

The degeneracy of the eigenvalues of the adjacency matrix of graphs may be broken by non-uniform changes of the edge weights. This symmetry breaking is the graph-theoretical equivalent of the molecular Jahn–Teller effect (Ceulemans et al. in Proc Roy Soc 468:971–989, 2012). It is investigated for three representative graphs, which all have the symmetric group on 5 elements, S ₅ , as automorphism group: the complete graph K₅, with 5 nodes, the Petersen graph, with 10 nodes, and an extended K₅ graph with 20 nodes. The spectra of these graphs contain fourfold, fivefold, and sixfold degenerate manifolds, respectively, and provide model systems for the study of the Jahn–Teller effect in icosahedral molecules. The S ₅ symmetries of the distortion modes of the quintuplet in the Petersen graph yield a resolution of the product multiplicity in the corresponding $ H \otimes \left( {g + 2h} \right) $ icosahedral Jahn–Teller problem. In the extended Petersen graph with 20 nodes, a selection rule prevents the Jahn–Teller splitting of the sextuplet into two conjugate icosahedral triplets.     

Scaffold topologies. 1. Exhaustive enumeration up to eight rings

Mapping the chemical space of small organic molecules is approached from a theoretical graph theory viewpoint, in an effort to begin the systematic exploration of molecular topologies. We present an algorithm for exhaustive generation of scaffold topologies with up to eight rings and an efficient comparison method for graphs within this class. This method uses the return index, a topological invariant derived from the adjacency matrix of the graph. Furthermore, we describe an algorithm that verifies the adequacy of the comparison method. Applications of this method for chemical space exploration in the context of drug discovery are discussed. The key result is a unique characterization of scaffold topologies, which may lead to more efficient ways to query large chemical databases.     

Correlations: Alkylsilane property — polynomial coefficients of the adjacency matrix of the molecular graph

Based on the characteristic polynomial coefficients (CPCs) of the adjacency matrix A′ of heterogeneous molecular graphs of the molecules containing a tetravalent heteroatom >Si< (>Ge<, >Sn<), etc. in the chain, a 13-constant additive scheme for the calculation of their physicochemical properties is obtained. The structural meaning of CPCs of the adjacency matrix A′ is established. By the formula obtained the formation enthalpies Δ _f H _{gas, 298K} ⁰ of SiC _n H_2n+2 alkylsilanes not studied experimentally are calculated.