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.     

Extremal (<Emphasis Type="Italic">n</Emphasis>,<Emphasis Type="Italic">n</Emphasis> + 1)-graphs with respected to zeroth- order general Randić index

A (n, n + 1)-graph G is a connected simple graph with n vertices and n + 1 edges. If d _v denotes the degree of the vertex v, then the zeroth-order general Randić index of the graph G is defined as , where α is a real number. We characterize, for any α, the (n,n + 1)-graphs with the smallest and greatest zeroth-order general Randić index.     

The (n,n)-graphs with the first three extremal Wiener indices

Let G = (V, E) be a simple connected graph with vertex set V and edge set E. The Wiener index W(G) of G is the sum of distances between all pairs of vertices in G, i.e., , where d _G (u, v) is the distance between vertices u and v in G. In this paper, we first give a new formula for calculating the Wiener index of an (n,n)-graph according its structure, and then characterize the (n,n)-graphs with the first three smallest and largest Wiener indices by this formula.     

Sharp upper bounds for total π-electron energy of alternant hydrocarbons

The energy E(G) of a graph G is defined as the sum of the absolute values of all the eigenvalues of the adjacency matrix of the graph G. This quantity is used in chemistry to approximate the total π-electron energy of molecules and in particular, in case G is bipartite, alternant hydrocarbons. In this paper, we show that if G = (V ₁, V ₂; E) is a bipartite graph with edges and , then

Unicyclic Graphs Possessing Kekulé Structures with Minimal Energy

Unicyclic graphs possessing Kekulé structures with minimal energy are considered. Let n and l be the numbers of vertices of graph and cycle C _l contained in the graph, respectively; r and j positive integers. It is mathematically verified that for and l = 2r + 1 or has the minimal energy in the graphs exclusive of , where is a graph obtained by attaching one pendant edge to each of any two adjacent vertices of C ₄ and then by attaching n/2 − 3 paths of length 2 to one of the two vertices; is a graph obtained by attaching one pendant edge and n/2 − 2 paths of length 2 to one vertex of C ₃. In addition, we claim that for has the minimal energy among all the graphs considered while for has the minimal energy.      

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.     

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.     

Extremal Polyomino Chains on k-matchings and k-independent Sets

Denote by the set of polyomino chains with n squares. For any , let m _k (T _n ) and i _k (T _n ) be the number of k-matchings and k-independent sets of T _n , respectively. In this paper, we show that for any polyomino chain and any , and , with the left equalities holding for all k only if T _n =L _n , and the right equalities holding for all k only if T _n =Z _n , where L _n and Z _n are the linear chain and the zig-zag chain, respectively. This work is supported by NNSFC (10371102).     

Minimal energy of unicyclic graphs of a given diameter

The energy of a graph is defined as the sum of the absolute values of all the eigenvalues of the graph. For a given positive integer d with , we characterize the graphs with minimal energy in the class of unicyclic graphs with n vertices and a given diameter d.      

An Upper Bound for the Clar Number of Fullerene Graphs

A fullerene graph is a three-regular and three-connected plane graph exactly 12 faces of which are pentagons and the remaining faces are hexagons. Let F _n be a fullerene graph with n vertices. The Clar number c(F _n ) of F _n is the maximum size of sextet patterns, the sets of disjoint hexagons which are all M-alternating for a perfect matching (or Kekulé structure) M of F _n . A sharp upper bound of Clar number for any fullerene graphs is obtained in this article: . Two famous members of fullerenes C₆₀ (Buckministerfullerene) and C₇₀ achieve this upper bound. There exist infinitely many fullerene graphs achieving this upper bound among zigzag and armchair carbon nanotubes.     

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

Unicycle Graphs with Maximum Generalized Topological Indices

Let G be an unicycle graph and d _v the degree of the vertex v. In this paper, we investigate the following topological indices for an unicycle graph , , where m ≥ 2 is an integer. All unicycle graphs with the largest values of the three topological indices are characterized. This research is supported by the National Natural Science Foundation of China(10471037)and the Education Committee of Hunan Province(02C210)(04B047).     

On the largest eigenvalues of trees with perfect matchings

Let λ₁ (G) and Δ (G), respectively, denote the largest eigenvalue and the maximum degree of a graph G. Let be the set of trees with perfect matchings on 2m vertices, and . Among the trees in , we characterize the tree which alone minimizes the largest eigenvalue, as well as the tree which alone maximizes the largest eigenvalue when . Furthermore, it is proved that, for two trees T ₁ and T ₂ in (m≥ 4), if and Δ (T ₁) > Δ (T ₂), then λ₁ (T ₁) > λ₁ (T ₂).     

A Method of Computing the PI Index of Benzenoid Hydrocarbons Using Orthogonal Cuts

The Padmakar–Ivan (PI) index of a graph G is defined as PI , where for edge e=(u,v) are the number of edges of G lying closer to u than v, and is the number of edges of G lying closer to v than u and summation goes over all edges of G. The PI index is a Wiener–Szeged-like topological index developed very recently. In this paper, we describe a method of computing PI index of benzenoid hydrocarbons (H) using orthogonal cuts. The method requires the finding of number of edges in the orthogonal cuts in a benzenoid system (H) and the edge number of H – a task significantly simpler than the calculation of PI index directly from its definition. On the eve of 70th anniversary of both Prof. Padmakar V. Khadikar and his wife Mrs. Kusum Khadikar.     

On zeroth-order general Randić index of conjugated unicyclic graphs

Let G be a graph and d _v denote the degree of the vertex v in G. The zeroth-order general Randić index of a graph is defined as where α is an arbitrary real number. In this paper, we investigate the zeroth-order general Randić index of conjugated unicyclic graphs G (i.e., unicyclic graphs with a perfect matching) and sharp lower and upper bounds are obtained for depending on α in different intervals.     

On minimal energies of trees of a prescribed diameter

The energy of a graph is defined as the sum of the absolute values of all the eigenvalues of the graph. Let denote the set of trees on n vertices and diameter d, . Yan and Ye [Appl. Math. Lett. 18 (2005) 1046–1052] have recently determined the unique tree in with minimal energy. In this article, the trees in with second-minimal energy are characterizedAMS Subject Classification: 05C50, 05C35     

Hosoya polynomials of TUC4C8(S) nanotubes

The Hosoya polynomial of a chemical graph G is , where d _G (u, v) denotes the distance between vertices u and v. In this paper, we obtain analytical expressions for Hosoya polynomials of TUC₄C₈(S) nanotubes. Accordingly, the Wiener index, obtained by Diudea et al. (MATCH Commun. Math. Comput. Chem. 50, 133–144, (2004)), and the hyper-Wiener index are derived. This work is supported by the Fundamental Research Fund for Physics and Mathematic of Lanzhou University (Grant No. LZULL200809).     

New upper bounds on Zagreb indices

The first Zagreb index M ₁(G) is equal to the sum of squares of the degrees of the vertices, and the second Zagreb index M ₂(G) is equal to the sum of the products of the degrees of pairs of adjacent vertices of the underlying molecular graph G. In this paper we obtain an upper bound on the first Zagreb index M ₁(G) of G in terms of the number of vertices (n), number of edges (m), maximum vertex degree (Δ₁), second maximum vertex degree (Δ₂) and minimum vertex degree (δ). Using this result we find an upper bound on M ₂(G). Moreover, we present upper bounds on and in terms of n,  m, Δ₁, Δ₂, δ, where denotes the complement of G.     

On the path-Zagreb matrix

The definition of the path-Zagreb matrix for (chemical) trees PZ and its generalization to any (molecular) graph is presented. Additionally, the upper bound of , where G _n is a graph with n vertices is given.