Two Types Of Graphic Polynomials And Associated Graphic Indices

The characteristic polynomial of a adjacent matrix of a graph and its spectral radius of a graph has been intensively studied by many mathematician in [18]-[19],[66],[95],[67]. It has many interesting combinatorial information and have graph structural properties. Since the adjacent matrix and the signless Lapladan matrix are symmetric nonnegative matrices, matrices are useful tools to study the associated graphs properties and graphs also are tools to study the matrix properties, see [93] and [75].Cvetkovic, Doob, Gutman, Torgasev,[18](Ch.4.) denote the matching poly-nomial as where m(G, k) is the number of k-matching of a graph G and M(G) is the largest matching root of MG (x). The matching polynomial is also independently discovered in statistical physics and in a mathematical context. In statistical physics it was first considered by Heilman and Lieb in1970in [62] and soon after by Kunz and Gruber [72].The matching polynomial of a graph can be presented by the characteristic polynomial of some special type of graphic matrix, i.e., Godsil and Gutman [40], Yan [121], F. M. Dong [23], etc. Therefore, the matching polynomial and the char-acteristic polynomial of a graph has some similar properties. As we known that M(G)≤p(G), the equality holds if and only if G is a tree [41].In1983, Gutman and Harary [50] define the independence polynomial as where α(G, k) is the number of stable sets of a graph with k vertices. For con-venience, we set α(G,0)=1. In addition, a(G,1)=|V(G)|is the number of vertices of G. Clearly, a(G, k)=0if k> n. After that many important results have been found. Fisher and Brown have studied the roots of the independence polynomials of graphs ([9],[34]). Alavi, Malde, Schwenk, Mandrecu and Erdos have studied the properties of its coefficients in [3],[83].In1971the Japanese chemist Haruo Hosoya introduced a molecular-graph based structure descriptor [58], which he named topological index and denoted by Z(G). which is the summation of the coefficients of the matching polynomial of struc-ture of molecule. He showed that certain physio-chemical properties of alkane (saturated hydrocarbons), in particular, their boiling points are well correlated with Z(G). Hosoya and his coworkers and other researchers showed that the in-dex Z(G) is related with a variety of physio-chemical properties of alkane and it is also used in the theory of conjugated π-electron system. Other applications of Z(G) were also attempted in [83]. Beside it is used in mathematical chemistry for quantifying relevant details of molecular structure, in recent years, a lot of works has been done on determining the graph within a prescribed class of graphs that minimize or maximize the value of the index. The Hosoya index relate to the eigenvalues of a adjacent matrix of a graph [37], relate to the degree of vertex,2-degree of vertex [61], and relate to other graph index like Wiener index [110] as well.In1980, American chemist Richard E. Merrifield and Howard E. Simmons elaborated a theory aimed at describing molecular structure by means of finite-set topology. It is known as the Merrifield-Simmons index, denoted by σ(G) in [89]-[92]. It is connected with various properties of alkane, for example, the boiling point, entropy, and heat of vaporization, etc.. Balasubramanian [6] studied the resistance energy of molecules, where xj, xjac are the eigenvalues of the structure of molecules and the roots of the matching polynomial of the structure of molecules, gj, hj are the number of elec-tronic number and j level and occupation number. Therefore, these polynomial and related indices has many applications in physics, chemistry and biology.In chapter2, we mainly investigate the properties of paths, cycles and some other type of graphs. By the basic computer formulas of matching polynomial of a graph (Property4, P.7), all matching polynomial of graphs can be expressed by the combinatorial of matching polynomial of paths. Therefore these relations are used to comparing the largest matching root, characterizing the co-matching graphs. We also investigate the largest matching root of unicyclic graphs, bipar-tite graphs, graphs with fixed edge cut numbers and graphs with given connec-tivity. We characterize the extremal graph with respect to largest matching root. In the end of this chapter section2.8we investigate the graphs with6distinct matching roots and investigate the co-matching and matching unique graphs.In chapter3, we give expressions for the first four coefficients of indepen-dence polynomials of graphs. We also investigate the independence polynomials of paths and cycles and some other graphs. We give an upper bound for the min-imal root of the independence polynomial of simple graph with respect to the independence number, order and size of a graph. Secondly, we compare the co-efficients of independence polynomials of certain type of graphs, in the end we give a way to construct co-independence polynomial graphs. As we known for the Hosoya index of simple graphs, n=Z(Sn)≤Z(G)≤Z(Pn)=fn+i holds, where Sn and Pn are a star and a path on n vertices. As to Merrifield-Simmons index,2n-1+1=a(Sn)≥σ(G)≥σ(Kn)=n+1, where fn is the nth Fibonacci number. In chapter4, we mainly investigate the Hosoya indices and the Merrifield-Simmons indices under certain graph transformations and characterize the extremal graphs with respect to these indices. As an appli-cation of these results we complete characterize the largest matching root, the Hosoya index order of theta graphs the graphs with fixed matching number. In the chapter5we completely study the Hosoya index, Merrifield-Simmons index and compare the coefficients of matching polynomials and independence poly-nomials of chain of cycles and characterize the extremal graphs.