The graph center concept for polycyclic graphs

While the concept of the graph center is unambiguous (and quite old) in the case of acyclic graphs, an attempt has been made recently to extend the concept to polycyclic structures using the distance matrix of a graph as the basis. In this work we continue exploring such generalizations considering in addition to the distance matrix, self-avoiding walks or paths as graph invariants of potential interest for discriminating distinctive vertex environments in a graph of polycyclic structures. A hierachy of criteria is suggested that offers a systematic approach to the vertex discrimination and eventually establishes in most cases the graph center as a single vertex, a single bond (edge), or a single group of equivalent vertices. Some applications and the significance of the concept of the graph center are presented.     

Common vertex matrix: A novel characterization of molecular graphs by counting

We present a novel matrix representation of graphs based on the count of equal‐distance common vertices to each pair of vertices in a graph. The element (i, j) of this matrix is defined as the number of vertices at the same distance from vertices (i, j). As illustrated on smaller alkanes, these novel matrices are very sensitive to molecular branching and the distribution of vertices in a graph. In particular, we show that ordered row sums of these novel matrices can facilitate solving graph isomorphism for acyclic graphs. This has been illustrated on all undecane isomers C₁₁H₂₄ having the same path counts (total of 25 molecules), on pair of graphs on 18 vertices having the same distance degree sequences (Slater's graphs), as well as two graphs on 21 vertices having identical several topological indices derived from information on distances between vertices. © 2013 Wiley Periodicals, Inc.     

A simple algorithm for unique representation of chemical structures-cyclic/acyclic functionalized achiral molecules

An algorithm, based on "vertex priority values" has been proposed to uniquely sequence and represent connectivity matrices of chemical structures of cyclic/acyclic functionalized achiral hydrocarbons and their derivatives. In this method, "vertex priority values" have been assigned in terms of atomic weights, subgraph lengths, loops, and heteroatom contents. Subsequently, the terminal vertices have been considered upon completing the sequencing of the core vertices. This approach provides a multilayered connectivity graph, which can be put to use in comparing two or more structures or parts thereof for any given purpose. Furthermore, the basic vertex connection tables generated here are useful in the computation of characteristic matrices/topological indices and automorphism groups and in storing, sorting, and retrieving chemical structures from databases.     

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.     

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.     

The characteristic polynomials of structures with pending bonds

It is well known [1] that the calculation of characteristic polynomials of graphs of interest in Chemistry which are of any size is usually extremely tedious except for graphs having a vertex of degree 1. This is primarily because of numerous combinations of contributions whether they were arrived at by non-imaginative expansion of the secular determinant or by the use of some of the available graph theoretical schemes based on the enumeration of partial coverings of a graph, etc. An efficient and quite general technique is outlined here for compounds that have pending bonds (i.e., bonds which have a terminal vertex). We have extended here the step-wise pruning of pending bonds developed for acyclic structures by one of the authors [2] for elegant evaluation of the characteristic polynomials of trees by accelerating this process, treating pending group as a unit. Further, it is demonstrated that this generalized pruning technique can be applied not only to trees but to cyclic and polycyclic graphs of any size. This technique reduces the secular determinant to a considerable extent. The present technique cannot handle only polycyclic structures that have no pending bonds. However, frequently such structures can be reduced to a combination of polycyclic graphs with pending bonds [3] so that the present scheme is applicable to these structures too. Thus we have arrived at an efficient and quite a simple technique for the construction of the characteristic polynomials of graphs of any size.     

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.     

Unusual random walks

For most structures (molecules, graphs, lattices) a count of random walks for nonequivalent sites will give different numbers, particularly for walks of many steps. Occasionally one finds the same count of walks for nonequivalent sites. These have been termed “unusual walks” and have been closely examined in the case of trivalent graphs. While it remains to be understood what structural factors are critical, some regularities have been observed and are discussed. Unusual walks within a single structure signal “isospectural” points in a graph. A number of structures possessing unusual walks have been displayed, and a few constructive steps which do not alter the “unusual” characteristics of selected vertices have been indicated.     

Characterization of molecular complexity

We put forward a novel index of molecular complexity, ξ, taking into account the symmetry of a molecular graph and the specificity of structural components considered. The ξ index is defined as the sum of augmented valences of all mutually nonequivalent vertices in a molecular graph. The augmented valence of a vertex in a graph is the sum of its valence and valences of all neighboring vertices with the weight 1/2^d depending on their distance, d, from the vertex. The ξ index is examined on the set of octane isomers and some special classes of graphs. It is also compared with a certain number of alternative complexity measures considered in the literature. © 2002 Wiley Periodicals, Inc. Int J Quantum Chem, 2003     

The overall Wiener index--a new tool for characterization of molecular topology.

Recently, the concept of overall connectivity of a graph G, TC(G), was introduced as the sum of vertex degrees of all subgraphs of G. The approach of more detailed characterization of molecular topology by accounting for all substructures is extended here to the concept of overall distance OW(G) of a graph G, defined as the sum of distances in all subgraphs of G, as well as the sum of eth-order terms, (e)OW(G), with e being the number of edges in the subgraph. Analytical expressions are presented for OW(G) of several basic classes of graphs. The overall distance is analyzed as a measure of topological complexity in acyclic and cyclic structures. The potential usefulness of the components of this generalized Wiener index in QSPR/QSAR is evaluated by its correlation with a number of properties of C3-C8 alkanes and by a favorable comparison with models based on molecular connectivity indices.     

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.     

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.     

Method for construction of characteristic polynomials via graph linearization

A new method for construction of characteristic polynomials (CP) of complicated graphs having arbitrary edge and vertex weights has been developed. The method first converts the graph into isospectral linear chains with weighted vertices and edges and then builds up the CP coefficients recursively. Two types of graphs have been used for illustration, viz., (i) graphs that can be linearized by symmetry factorization and (ii) graphs without symmetry which are to be linearized by an algorithm involving walks of unit length. Both types have been illustrated, of which type (i) includes the Schlegel of fullerene fragment C₂₀ and another large graph with many fused rings. © 1997 John Wiley & Sons, Inc. Int J Quant Chem 65 : 199–204, 1997     

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     

A novel approach to the use of graph theory in structure–activity relationship studies. Application to the qualitative evaluation of mutagenicity in a series of nonfused ring aromatic compounds

In this article we describe a novel approach to the application of graph theory in structure–activity relationship studies. An information–theoretical topological index for the vertices of a molecular graph has been used for the qualitative evaluation of the mutagenic activity of a series of nonfused ring aromatic compounds. The use of a vertex index contrasts with the conventional approach of using a topological index for the entire molecule. The idea is to identify regions, or substructures in the molecules (molecular graphs) which may be used to determine certain biological activity of chemical compounds. The results obtained in this paper indicate that the present approach is capable of classifying the mutagenic activity of the compounds under consideration and may find useful application in structure–activity relationship studies of diverse bioactive compounds.     

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 acyclic graphs based on local vertex invariants and topological indices. Derived canonical labelling and coding of trees and alkanes

A new procedure (GENLOIS) is presented for generating trees or certain classes of trees such as 4-trees (graphs representing alkanes), identity trees, homeomorphical irreducible trees, rooted trees, trees labelled on a certain vertex (primary, secondary, tertiary, etc.). The present method differs from previous procedures by differentiating among the vertices of a given parent graph by means of local vertex invariants (LOVIs). New graphs are efficiently generated by adding points and/or edges only to non-equivalent vertices of the parent graph. Redundant generation of graphs is minimized and checked by means of highly discriminating, recently devised topological indices based either on LOVIs or on the information content of LOVIs. All trees onN + 1 (N + 1 < 17) points could thus be generated from the complete set of trees onN points. A unique cooperative labelling for trees results as a consequence of the generation scheme. This labelling can be translated into a code for which canonical rules were recently stated by A.T. Balaban. This coding appears to be one of the best procedures for encoding, retrieving or ordering the molecular structure of trees (or alkanes).Dedicated to Professor Alexandru T. Balaban on the occasion of his 60th anniversary.     

Discrimination of isomeric structures using information theoretic topological indices

Three newly defined information theoretic topological indices, namely “degree complexity (I^d),” “graph vertex complexity (H^V),” and “graph distance complexity (H^D)” along with three other information indices have been used to study their discriminating power of 45 trees and 19 monocyclic graphs. It is found that the newly defined indices have satisfactory discriminating power while H^D has been found to be the only index to discriminate all the graphs studied.