Maximum energy trees with two maximum degree vertices

The energy E of a graph G is equal to the sum of the absolute values of the eigenvalues of G. In 2005 Lin et al. determined the trees with a given maximum vertex degree Δ and maximum E, that happen to be trees with a single vertex of degree Δ. We now offer a simple proof of this result and, in addition, characterize the maximum energy trees having two vertices of maximum degree Δ.     

On the connectivity index of trees

The connectivity index χ₁(G) of a 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. Let T(n, r) be the set of trees on n vertices with diameter r. In this paper, we determine all trees in T(n, r) with the largest and the second largest connectivity index. Also, the trees in T(n, r) with the largest and the second largest connectivity index are characterized. Mei Lu is partially supported by NNSFC (No. 10571105).     

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).      

Vertex topological indices and tree expressions,generalizations of continued fractions

We expand on the work of Hosoya to describe a generalization of continued fractions called “tree expressions.” Each rooted tree will be shown to correspond to a unique tree expression which can be evaluated as a rational number (not necessarily in lowest terms) whose numerator is equal to the Hosoya index of the entire tree and whose denominator is equal to the tree with the root deleted. In the development, we use Z(G) to define a natural candidate ζ(G, v) for a “vertex topological index” which is a value applied to each vertex of a graph, rather than a value assigned to the graph overall. Finally, we generalize the notion of tree expression to “labeled tree expressions” that correspond to labeled trees and show that such expressions can be evaluated as quotients of determinants of matrices that resemble adjacency matrices.     

On the Randić Index of Quasi-tree Graphs

The Randić index of an organic molecule whose molecular graph is G is the sum of the weights (d(u)d(v))^−1/2 of all edges uv of G, where d(u) and d(v) are the degrees of the vertex u and v in G. A graph G is called quasi-tree, if there exists such that G − u is a tree. In the paper, we give sharp lower and upper bounds on the Randić index of quasi-tree graphs. Mei Lu: Partially supported by NSFC (No. 10571105).     

Graphs with maximum connectivity index

Let G be a graph and d_v the degree (=number of first neighbors) of its vertex v. The connectivity index of G is χ=∑ (d_ud_v)^−1/2, with the summation ranging over all pairs of adjacent vertices of G. In a previous paper (Comput. Chem. 23 (1999) 469), by applying a heuristic combinatorial optimization algorithm, the structure of chemical trees possessing extremal (maximum and minimum) values of χ was determined. It was demonstrated that the path P_n is the n-vertex tree with maximum χ-value. We now offer an alternative approach to finding (molecular) graphs with maximum χ, from which the extremality of P_n follows as a special case. By eliminating a flaw in the earlier proof, we demonstrate that there exist cases when χ does not provide a correct measure of branching: we find pairs of trees T, T′, such that T is more branched than T′, but χ(T)>χ(T′). The smallest such examples are trees with 36 vertices in which one vertex has degree 31.     

The first and second largest Merrifield–Simmons indices of trees with prescribed pendent vertices

The Merrifield–Simmons index of a graph G is defined as the number of subsets of the vertex set, in which any two vertices are non-adjacent, i.e., the number of independent-vertex sets of G. By T(n,k) we denote the set of trees with n vertices and with k pendent vertices. In this paper, we investigate the Merrifield–Simmons index for a tree T in T(n,k). For all trees in T(n,k), we determined unique trees with the first and second largest Merrifield–Simmons index, respectively.     

On the Randić Index of Acyclic Conjugated Molecules

The Randić index of an organic molecule whose molecular graph is G is the sum of the weights (d(u)d(v))^−1/2 of all edges uv of G, where d(u) and d(v) are the degrees of the vertices u and v in G. We give a sharp lower bound on the Randić index of conjugated trees (trees with a perfect matching) in terms of the number of vertices. A sharp lower bound on the Randić index of trees with a given size of matching is also given Mei Lu: Partially supported by NNSFC (No. 60172005) Lian-zhu Zhang: Partially supported by NNSFC (No. 10271105) Feng Tian: Partially supported by NNSFC (No. 10431020)     

Conjugated chemical trees with minimal energy and prescribed diameter

The energy of a molecular graph G is defined as the sum of the absolute values of the eigenvalues of A(G), where A(G) is the adjacency matrix of this graph. This article characterizes conjugated chemical trees with prescribed diameter and minimal energies and presents explicit expressions of their Hosoya indices. © 2006 Wiley Periodicals, Inc. Int J Quantum Chem, 2006     

Some upper bounds for the energy of graphs

Let G = (V,E) be a graph with n vertices and e edges. Denote V(G) = {v ₁,v ₂,...,v _n }. The 2-degree of v _i , denoted by t _i , is the sum of degrees of the vertices adjacent to . Let σ _i be the sum of the 2-degree of vertices adjacent to v _i . In this paper, we present two sharp upper bounds for the energy of G in terms of n, e, t _i , and σ _i , from which we can get some known results. Also we give a sharp bound for the energy of a forest, from which we can improve some known results for trees.     

On graph isomorphism and graph automorphism

The problem of graph isomorphism, graph automorphism and a unique graph ID is considered. A new approach to the solution of these problems is suggested. The method is based on the spectral decompositionA = _{i i} K _iof the adjacency matrixA. This decomposition is independent of the particular labeling of graph vertices, and using this decomposition one can formulate an algorithm to derive a canonical labeling of the corresponding graphG. Since the spectral decomposition uniquely determines the adjacency matrixA and hence graphG, the obtained canonical labeling can be used in order to derive a unique graph ID. In addition, if the algorithm produces several canonical labelings, all these labelings and only these labelings are connected by the elements of the graph automorphism groupG. In this way, one obtains all elements of this group. Concerning graph isomorphism, one can use a unique graph ID obtained in the above way. However, the algorithm to decide whether graphG andG are isomorphic can be substantially improved if this algorithm is based on the direct comparison between spectral decompositions of the corresponding adjacency matricesA andA.Research supported by the Yugoslav Ministry for Development (Grant P-339).     

PI indices of pericondensed benzenoid graphs

The Padmakar–Ivan (PI) index is a graph invariant defined as the summation of the sums of n _eu (e|G) and n _ev (e|G) over all the edges e = uv of a connected graph G, i.e., , where n _eu (e|G) is the number of edges of G lying closer to u than to v and n _ev (e|G) is the number of edges of G lying closer to v than to u. An efficient formula for calculating the PI index of a class of pericondensed benzenoid graphs consisting of three rows of hexagonal of various lengths.     

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.     

Calculating the number of spanning trees in a labeled planar molecular graph whose inner dual is a tree

The quantum mechanical relevance of the concept of a spanning tree extant within a given molecular graph—specifically, one that may be considered to represent the carbon-atom connectivity of a particular (planar) conjugated system—was first explicitly pointed out by Professor Roy McWeeny in his now-classic 1958 memoire entitled “Ring Currents and Proton Magnetic Resonance in Aromatic Molecules.” In a recent work, Gutman and one of the present authors proposed a scheme for calculating the number of spanning trees in the graph associated with catacondensed, benzenoid molecules which, by definition, contain rings of just the one size (six-membered); here, we present an algorithmic approach that enables the determination of the number of spanning trees in the molecular graph of any catacondensed system (which, in general, has rings of more than one size, and these may be of any size). An illustrative example is given, in which the algorithm devised is applied to a (hypothetical) pentacyclic catacondensed structure comprising a five-membered ring, a six-membered ring, a seven-membered ring, and two four-membered rings. © 1996 John Wiley & Sons, Inc.     

On molecular topological properties of hex‐derived networks

Topological indices are numerical parameters of a molecular graph, which characterize its topology and are usually graph invariant. In quantitative structure–activity relationship/quantitative structure–property relationship study, physico‐chemical properties and topological indices such as Randić, atom–bond connectivity (ABC), and geometric–arithmetic (GA) index are used to predict the bioactivity of chemical compounds. Graph theory has found a considerable use in this area of research. In this paper, we study hex‐derived networks HDN1(n) and HDN2(n), which are generated by hexagonal network of dimension n and derive analytical closed results of general Randić index R_α(G) for different values of α, for these networks of dimension n. We also compute the general first Zagreb, ABC, GA, ABC₄, and GA₅ indices for these hex‐derived networks for the first time and give closed formulae of these degree‐based indices for hex‐derived networks. Copyright © 2016 John Wiley & Sons, Ltd.     

A note on the cyclical edge-connectivity of fullerene graphs

A fullerene graph is a 3-regular (cubic) and 3-connected spherical graph that has exactly 12 pentagonal faces and other hexagonal faces. The cyclical edge-connectivity of a graph G is the maximum integer k such that G cannot be separated into two components, each containing a cycle, by deletion of fewer than k edges. Došlić proved that the cyclical edge-connectivity of every fullerene graph is equal to 5. By using Euler’s formula, we give a simplified proof, mending a small oversight in Došlić’s proof. Further, it is proved that the cyclical connectivity of every fullerene graph is also equal to 5.     

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).