Harary index of Eulerian graphs

Journal of Mathematical Chemistry - The Harary index of a connected (molecular) graph is defined as the sum of reciprocals of distances between all its pairs of vertices. In this paper, we...     

On Harary index

We report lower and upper bounds for the Harary index of a connected (molecular) graph, and, in particular, upper bounds of triangle- and quadrangle-free graphs. We also give the Nordhaus–Gaddum-type result for the Harary index. Dedicated to the memory of Professor Frank Harary (1921–2005), the late grandmaster of both graph theory and chemical graph theory.     

Bounds on Harary index

In this paper, we obtain the lower and upper bounds on the Harary index of a connected graph (molecular graph), and, in particular, of a triangle- and quadrangle-free graphs in terms of the number of vertices, the number of edges and the diameter. We give the Nordhaus–Gaddum-type result for Harary index using the diameters of the graph and its complement. Moreover, we compare Harary index and reciprocal complementary Wiener number for graphs.     

On the Kirchhoff index of regular graphs

Using probabilistic tools, we give a compact formula for the Kirchhoff index of any d‐regular N‐vertex graph in terms of d, N, and Kemeny's constant, as well as general upper and lower bounds in terms of d and N. © 2009 Wiley Periodicals, Inc. Int J Quantum Chem, 2010     

Ordering chemical unicyclic graphs by Wiener polarity index

Suppose G is a chemical graph with vertex set V(G). Define D(G) = {{u, v} ⊆ V (G) | d _G (u, v) = 3}, where d _G (u, v) denotes the length of the shortest path between u and v. The Wiener polarity index of G, W _p (G), is defined as the size of D(G). In this article, an ordering of chemical unicyclic graphs of order n with respect to the Wiener polarity index is given.     

On the ABC index of connected graphs with given degree sequences

The atom-bond connectivity (ABC) index of a graph G is defined to be \(ABC(G)=\sum _{uv\in E(G)}\sqrt{\frac{d(u)+d(v)-2}{d(u)d(v)}}\) where d(u) is the degree of a vertex u. The ABC index plays a key role in correlating the physical–chemical properties and the molecular structures of some families of compounds. In this paper, we describe the structural properties of graphs which have the minimum ABC index among all connected graphs with a given degree sequence. Moreover, these results are used to characterize the extremal graphs which have the minimum ABC index among all unicyclic and bicyclic graphs with a given degree sequence.     

Stereotopological indices for a family of chemical graphs

We describe a mathematical method that can be employed to define stereotopological indices of placements of certain graphs in space. These indices are applied to successfully distinguish between configurations in a chemically interesting family of knotted and/or linked four-valent oriented graphs in space. The methods are fundamentally algebraic and combinatorial in nature and are most readily understood in the context of calculations and the study of several key examples that are presented.     

Symmetry groups of chemical graphs

The symmetry groups of all trees are shown to be expressible as generalized wreath products by a tree pruning algorithm. The symmetry groups of certain cyclic graphs which can be expresssed as generalized compositions are also shown to be generalized wreath products. The symmetry groups of complete multipartite graphs can be obtained in a similar manner. Character tables of symmetry groups of certain chemical graphs are also obtained.     

Homomorphism polynomials of chemical graphs

We say that a graphG ishomomorphic to a graphH if there is a mappingp from the vertices of G onto the vertices ofH such thatp(u) andp() are adjacent inH wheneveru and are adjacent in G. Thehomomorphism polynomial of a graphG is a polynomial in two variables that counts the number of homomorphisms ofG onto the complete graph of each order. This polynomial can be computed recursively in an analog to the chromatic polynomial. In this paper, we present some results regarding the homomorphism polynomials of the graphs of chemical compounds — in particular, alkane isomers. The coefficients of the homomorphism polynomial can be used to predict the rankings of compounds with respect to several chemical properties. Our results seem to refine those obtained by Randi et al. from path lengths.     

Three methods for calculation of the hyper-Wiener index of molecular graphs

The hyper-Wiener index WW of a graph G is defined as WW(G) = (summation operator d (u, v)(2) + summation operator d (u, v))/2, where d (u, v) denotes the distance between the vertices u and v in the graph G and the summations run over all (unordered) pairs of vertices of G. We consider three different methods for calculating the hyper-Wiener index of molecular graphs: the cut method, the method of Hosoya polynomials, and the interpolation method. Along the way we obtain new closed-form expressions for the WW of linear phenylenes, cyclic phenylenes, poly(azulenes), and several families of periodic hexagonal chains. We also verify some previously known (but not mathematically proved) formulas.     

Symmetry properties of chemical graphs VIII. On complementarity of isomerization modes

Isomerization mode defines the process of interconversion of one isomer into another. Several mechanisms are conceivable for degenerate rearrangements and, in general, lead to a distinctive network of relations between participating isomers. Here we consider selected modes which are complementary in the sense that if mode 1 transforms an isomer A into B, C, D etc., then mode 2 transforms the same isomer A into X, Y, Z, etc., which includes all isomers not comprised by the first mode. Physico-chemical complementarity can be translated into mathematical complementarity of associated chemical graphs. This allows us to use the tool of Graph Theory. One example of graph theoretical use is the theorem that graph G and its complement G have the same automorphism group (i.e., the same symmetry). We have shown that a close examination of a graph and its complement and their components allows us to recognize the automorphism group in some complex cases without resorting to canonical numbering or other involved procedures, and even allows us to determine isomorphism of different processes.Dedicated to Professor Kurt Mislow of Princeton UniversityOperated for the U.S. Department of Energy by Iowa State University under contract W-7405-Eng-82. Supported in part by the Office of the Director.     

On the characterization of chemical surface groups of carbon materials

This paper deals with the use of several methods to characterize the chemical surface groups of carbon materials. Several samples embracing a wide range of acidic and basic characteristics have been used for this purpose. The quantitative determinations have been carried out by selective titrations in aqueous solutions, thermal programmed desorption connected to mass spectrometry (TPD-MS), and ammonia adsorption-desorption, measured by thermogravimetry (TG). The results show some inconsistencies between the different experimental methods. These mainly arise because chemical transformations can be produced during the experiments. Moreover, the textural characteristics of the carbon materials and the existence of pi electrons on the graphitic planes are important factors to be considered in the discussion of the results.     

Parallel algorithm for the computation of characteristic polynomials of chemical graphs

A parallel algorithm is developed for the first time based on Frame's method to compute the characteristic polynomials of chemical graphs. This algorithm can handle all types of graphs: ordinary, weighted, directed, and signed. Our algorithm takes only linear time in the CRCW PRAM model with O(n³) processors whereas the sequential algorithm takes O(n⁴) time. Especially when the number of vertices of the graph is large this method will be more efficient than the recently developed vectorized Frame and Givens–Householder methods.     

Important mathematical structures of the topological index Z for tree graphs

Mathematical importance of the topological index, ZG, or the so-called Hosoya index is stressed by presenting and giving supporting evidence for the proposed conjecture. That is, for a given pair of positive integers (n1or=3), with Z(G1) = n1 and Z(G2) = n2.     

On the z-counting polynomial for edge-weighted graphs

The construction of the Z-counting polynomial for edge-weighted graphs is discussed.Dedicated to Professor Haruo Hosoya (Tokyo) on the occasion of his 55th birthday for enriching chemical graph theory with the elegant concept of the Z-counting polynomial.     

Extended connectivity in chemical graphs

The true nature of the extended connectivity, used in Morgan algorithm for the canonical numerotation of points in chemical graphs, is discussed. An alternative method for its calculation based on the number of walks is described and shown to yield results identical to Morgan's method.     

Complexity index for the linear mechanisms of chemical reactions

A complexity measure is proposed for the kinetic models of chemical reactions with linear mechanisms. The index is related to the structure of fractional-rational kinetic laws for chemical reactions, as well as to the structure of cyclic graphs used to describe them. The complexity index is shown to be closely related to the detailed hierarchical classification and to the code of linear reaction mechanisms, recently introduced. A number of index properties are proved for two- and three-reaction routes. They reflect the influence of the various classification criteria, such as the number of reaction routes and intermediates, the type, class and subclasses of the mechanism, and the number of intermediates in each reaction route. Hierarchical levels of mechanisms with the same complexity (isocomplex mechanisms) are specified. Standard tables are presented with complexity indices for all topologically distinct linear reaction mechanisms having one to three reaction routes, two to six intermediates, and reversible elementary steps.[/p]     

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.