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.     

Topological analysis of eigenvectors of the adjacency matrices in graph theory: The concept of internal connectivity

The topological properties of eigenvectors of adjacency matrices of a graph have been analyzed. Model systems studied are n-vertex-m-edge (n-V-m-E) graphs where n = 2–4, m = 1–6. The topological information contained in these eigenvectors is described using vertex-signed and edge-signed graphs. Relative ordering of net signs of edge-signed graphs is similar to that of eigenvalues of the adjacency matrix. This simple analysis has also been applied to naphthalene, anthracene and pyrene. It provides a sound basis for the application of graph theory to molecular orbital theory.     

Hosoya index of unicyclic graphs with prescribed pendent vertices

The Hosoya index z(G) of a (molecular) graph G is defined as the total number of subsets of the edge set, in which any two edges are mutually independent, i.e., the total number of independent-edge sets of G. By G(n, l, k) we denote the set of unicyclic graphs on n vertices with girth and pendent vertices being resp. l and k. Let be the graph obtained by identifying the center of the star S _n-l+1 with any vertex of C _l . By we denote the graph obtained by identifying one pendent vertex of the path P _n-l-k+1 with one pendent vertex of . In this paper, we show that is the unique unicyclic graph with minimal Hosoya index among all graphs in G(n, l, k).      

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.     

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.     

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     

Some results on energy of unicyclic graphs with n vertices

A unicyclic graph is a connected graph whose number of edges is equal to the number of vertices. Hou (J Math Chem 29:163–168, 2001) first considered the minimal energy for general unicyclic graphs. In this paper, we determine the unicyclic graphs with the minimal energy in U_n^l{\mathcal {U}_n^l} and the unicyclic graphs with the first forth smallest energy in U_n (n 3 13){\mathcal {U}_n\,(n\geq 13)} vertices.     

On the spectral radius of graphs with connectivity at most <Emphasis Type="Italic">k</Emphasis>

In this paper, we study the spectral radius of graphs of order n with κ(G) ≤ k. We show that among those graphs, the maximal spectral radius is obtained uniquely at , which is the graph obtained by joining k edges from k vertices of K _n-1 to an isolated vertex. We also show that the spectral radius of will be very close to n − 2 for a fixed k and a sufficiently large n.     

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.     

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.     

On the Permanental Polynomials of Some Graphs

Let G be a simple graph with adjacency matrix A(G) and (G,x) the permanental polynomial of G. Let G × H denotes the Cartesian product of graphs G and H. Inspired by Kleins idea to compute the permanent of some matrices (Mol. Phy. 31 (3) (1976) 811–823), in this paper in terms of some orientation of graphs we study the permanental polynomial of a type of graphs. Here are some of our main results.1.If G is a bipartite graph containing no subgraph which is an even subdivision of K _2,3, then G has an orientation G ^e such that (G,x) = det (xI-A(G ^e )), where A(G ^e ) denotes the skew adjacency matrix of G ^e.2.Let G be a 2-connected outerplanar bipartite graph with n vertices. Then there exists a 2-connected outerplanar bipartite graph with 2n+2 vertices such that (G,x) is a factor of .3.Let T be an arbitrary tree with n vertices. Then , where ₁ , ₂ , ..., _n are the eigenvalues of T.     

On reciprocal reverse Wiener index

We report some properties, especially bounds for the reciprocal reverse Wiener index of a connected (molecular) graph. We find that the reciprocal reverse Wiener index possesses the minimum values for the complete graph in the class of n-vertex connected graphs and for the star in the class of n-vertex trees, and the maximum values for the complete graph with one edge deleted in the class of n-vertex connected graphs and for the tree obtained by attaching a pendant vertex to a pendant vertex of the star on n − 1 vertices in the class of n-vertex trees. These results are compared with those obtained for the ordinary Wiener index.     

Sharp Bounds for the Second Zagreb Index of Unicyclic Graphs

The second Zagreb index M ₂(G) of a (molecule) graph G is the sum of the weights d(u)d(v) of all edges uv of G, where d(u) denotes the degree of the vertex u. In this paper, we give sharp upper and lower bounds on the second Zagreb index of unicyclic graphs with n vertices and k pendant vertices. From which, and C _n have the maximum and minimum the second Zagreb index among all unicyclic graphs with n vertices, respectively.     

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     

The spread of unicyclic graphs with given size of maximum matchings

The spread s(G) of a graph G is defined as s(G) = max _i,j |λ _i − λ _j |, where the maximum is taken over all pairs of eigenvalues of G. Let U(n,k) denote the set of all unicyclic graphs on n vertices with a maximum matching of cardinality k, and U ^*(n,k) the set of triangle-free graphs in U(n,k). In this paper, we determine the graphs with the largest and second largest spectral radius in U ^*(n,k), and the graph with the largest spread in U(n,k).      

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.