A Complete Solution to a Conjecture on the β-Polynomials of Graphs

In 1990, Gutman and Mizoguchi conjectured that all roots of the -polynomial (G,C,x) of a graph G are real. Since then, there has been some literature intending to solve this conjecture. However, in all existing literature, only classes of graphs were found to show that the conjecture is true; for example, monocyclic graphs, bicyclic graphs, graphs such that no two circuits share a common edge, graphs without 3-matchings, etc, supporting the conjecture in some sense. Yet, no complete solution has been given. In this paper, we show that the conjecture is true for all graphs, and therefore completely solve this conjecture.     

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     

On reciprocal molecular topological index

We report some properties of the reciprocal molecular topological index RMTI of a connected graph, and, in particular, its relationship with the first Zagreb index M₁. We also derive the upper bounds for RMTI in terms of the number of vertices and the number of edges for various classes of graphs, including K _r+1 -free graphs with r ≥ 2, quadrangle-free graphs, and cacti. Additionally, we consider a Nordhaus-Gaddum-type result for RMTI.     

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.     

On the Ordering of a Class of Graphs with Respect to their Matching Numbers

Based on the number of k-matching m(G,k) of a graph G, Gutman and Zhang introduced an order relation of graphs: for graphs G ₁ and G ₂, if m(G ₁,k) ≥ m(G ₂,k) for all k. The order relation has important applications in comparing Hosaya indices and energies of molecular graphs and has been widely studied. Especially, Gutman and Zhang gave complete orders of six classes of graphs with respect to the relation . In this paper, we consider a class of graphs with special structure, which is a generalization of a class of graphs studied by Gutman and Zhang. Some order relations in the class of graphs are given, and the maximum and minimum elements with respect to the order relation are determined. The new results can be applied to order some classes of graphs by their matching numbers.     

Normal Components, Kekulé Patterns, and Clar Patterns in Plane Bipartite Graphs

As a general case of molecular graphs of polycyclic alternant hydrocarbons, we consider a plane bipartite graph G with a Kekulé pattern (perfect matching). An edge of G is called nonfixed if it belongs to some, but not all, perfect matchings of G. Several criteria in terms of resonant cells for determining whether G is elementary (i.e., without fixed edges) are reviewed. By applying perfect matching theory developed in plane bipartite graphs, in a unified and simpler way we study the decomposition of plane bipartite graphs with fixed edges into normal components, which is shown useful for resonance theory, in particular, cell and sextet polynomials. Further correspondence between the Kekulé patterns and Clar (resonant) patterns are revealed.     

The connective eccentricity index of graphs and its applications to octane isomers and benzenoid hydrocarbons

The connective eccentricity index (CEI) of a graph G is defined as , where ε_G(.) denotes the eccentricity of the corresponding vertex. The CEI obligates an influential ability, which is due to its estimating pharmaceutical properties. In this paper, we first characterize the extremal graphs with respect to the CEI among k-connected graphs (k-connected bipartite graphs) with a given diameter. Then, the sharp upper bound on the CEI of graphs with given connectivity and minimum degree (independence number) is determined. Finally, we calculate the CEI of two sets of molecular graphs: octane isomers and benzenoid hydrocarbons. We compare their CEI with some other distance-based topological indices through their correlations with the chemical properties. The linear model for the CEI is better than or as good as the models corresponding to the other distance-based indices.     

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     

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.     

On the three-fold irregular branched coverings of spatial four-valent graphs and its applications

LetL be a spatial four-valent graph. Then one of the effective tools for studying the topological position ofL in the 3-sphere is to consider the three-fold irregular branched coverings ofL [1]. In this paper we will show that this technique can also be applied to some hypothetical three-valent molecular graphs in topological stereochemistry.     

Functional groups expressed as graphs extracted from the Laplacian of the electron density

The valence charge concentration shell, as determined by the Laplacian of the electron density, is used as a source of quantum topological graphs, called L‐graphs. A considerable number of such graphs are extracted from the ab initio wave functions of 31 molecules calculated at the B3LYP/6‐311+G(2d,p)//B3LYP/6‐311+G(2d,p) level, covering common functional groups in organic chemistry. We show how L‐graphs can be constructed from a largely transferable subgraph called atomic L‐graph. We investigate the topological stability of the L‐graphs as a function of the basis set. Reliable and consistent atomic L‐graphs are only obtained with basis sets of triple‐zeta quality or higher. The recurrence of invariant motifs or subgraphs in the L‐graphs enables the isolation of 16 atomic L‐graphs. © 2003 Wiley Periodicals, Inc. Int J Quantum Chem, 2003     

A comparison between 1-factor count and resonant pattern count in plane non-bipartite graphs

The concept of resonant (or Clar) pattern is extended to a plane non-bipartite graph G in this paper: a set of disjoint interior faces of G is called a resonant pattern if such face boundaries are all M-conjugated cycles for some 1-factor (Kekulé structure or perfect matching) M of G. In particular, a resonant pattern of benzenoids and fullerenes coincides with a sextet pattern. By applying a novel approach, the principle of inclusion and exclusion in combinatorics, we show that for any plane graphs, 1-factor count is not less than the resonant pattern count, which generalize the corresponding results in benzenoid systems and plane bipartite graphs. Applications to fullerenes are also discussed.AMS Subject classification: 05C70, 05C90, 92E10     

Characterizations for Some Types of DNA Graphs

Vertex induced subgraphs of directed de Bruijn graphs with labels of fixed length k and over α letter alphabet are (α,k)-labelled. DNA graphs are (4,k)-labelled graphs. Pendavingh et al. proved that it is NP-hard to determine the smallest value α _k (D) for which a directed graph D can be (α _k (D),k)-labelled for any fixed . In this paper, we obtain the following formulas: and for cycle C _n and path P _n . Accordingly, we show that both cycles and paths are DNA graphs. Next we prove that rooted trees and self-adjoint digraphs admit a (Δ,k)-labelling for some positive integer k and they are DNA graphs if and only if Δ ≤ 4, where Δ is the maximum number in all out-degrees and in-degrees of such digraphs.     

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 lower bound on the number of elementary components of essentially disconnected generalized polyomino graphs

An essentially disconnected generalized polyomino graph is defined as a generalized polyomino graph with some perfect matchings and forbidden edges. The number of perfect matchings of a generalized polyomino graph G is the product of the number of perfect matchings of each elementary component in G. In this paper, we obtain a lower bound on the number of elementary components of essentially disconnected generalized polyomino graphs.     

Hückel and Möbius cyclic conjugated molecules

Generalized graphs represent Hückel-type and Möbius-type polycyclic conjugated systems. We show that the number of generalized graphs with different spectra for a given parent graph is not larger than 2 ^N(R) and is equal to 2 ^N(R) if no two rings are equivalent,N(R) being the number of rings (fundamental circuits) in the parent graph. We demonstrate that the rule for the stability of generalized graphs, proved in a previuos paper, and the information on the relative magnitudes of the effects of individual circuits enable one to predict the stabilities of generalized graphs without performing numerical calculations.     

Resistance distance in graphs and random walks

We study the resistance distance on connected undirected graphs, linking this concept to the fruitful area of random walks on graphs. We provide two short proofs of a general lower bound for the resistance, or Kirchhoff index, of graphs on N vertices, as well as an upper bound and a general formula to compute it exactly, whose complexity is that of inverting an N×N matrix. We argue that the formulas for the resistance in the case of the Platonic solids can be generalized to all distance‐transitive graphs. © 2001 John Wiley & Sons, Inc. Int J Quant Chem 81: 29–33, 2001     

Resistance distance local rules

In [D.J. Klein, Croat. Chem. Acta. 75(2), 633 (2002)] Klein established a number of sum rules to compute the resistance distance of an arbitrary graph, especially he gave a specific set of local sum rules that determined all resistance distances of a graph (saying the set of local sum rules is complete). Inspired by this result, we give another complete set of local rules, which is simple and also efficient, especially for distance-regular graphs. Finally some applications to chemical graphs (for example the Platonic solids as well as their vertex truncations, which include the graph of Buckminsterfullerene and the graph of boron nitride hetero-fullerenoid B ₁₂ N ₁₂) are made to illustrate our approach.     

Computer generation of characteristic polynomials of edge-weighted graphs,heterographs, and directed graphs

The computer code developed previously (K. Balasubramanian, J. Computational Chem., 5 , 387 (1984)) for the characteristic polynomials of ordinary (nonweighted) graphs is extended in this investigation to edge-weighted graphs, heterographs (vertex-weighted), graphs with loops, directed graphs, and signed graphs. This extension leads to a number of important applications of this code to several areas such as chemical kinetics, statistical mechanics, quantum chemistry of polymers, and unsaturated systems containing heteroatoms which include bond alternation. The characteristic polynomials of several edgeweighted graphs which may represent conjugated systems with bond alternations, heterographs (molecules with heteroatoms), directed graphs (chemical reaction network), and signed graphs and lattices are obtained for the first time.