关于图的两类多项式及相关指数的研究
|
摘要
设G为简单图,它的邻接矩阵记为A(G),A(G)的特征多项式称为图G的特征多项式,记为PG(x).A(G)的特征值和对应的重数称为图G的谱,记为,其中λ1=ρ(G)称为图的谱半径.对于图的谱性质的研究已经得到很多结果见[18]-[19],[66],[95]等.一个图的特征多项式的系数和图的谱包含了很多图的组合、结构性质.对于某类图来说,谱半径达到最大或者最小时的图被称为极图.如果两个图具有相同的谱,则它们被称为同谱图；如果某个图没有其他与其不同构的同谱图,则此图被称为是谱唯一的.图的谱性质在研究极图、同谱图和谱唯一图等方面有着重要的应用.连通图对应的邻接矩阵、无号拉普拉斯矩阵都是非负不可约的实对称矩阵,因此不可约矩阵的性质是研究图的谱的一个重要工具,同时图也是研究矩阵性质的一个模型,见文献[75],[93].
Cvetkovic, Doob, Gutman, Torgasev等人在[18][CH.4.]定义一个图的匹配多项式为：这里m(G,k)为G的k-匹配的数目,匹配多项式MG(x)的根为θ1,θ2,…,θs,并称θ1为最大匹配根,记为M(G).在统计物理学中最初由Heilman和Lieb[62]提出和研究,并由Kunz [72], Gruber等人进一步研究它的相关性质在物理学中的应用.匹配多项式常常可以用某种特殊构造的图的矩阵的特征多项式来表示,如Godsil和Gutman [40],Yan[121]等,因此图的匹配多项式的根和图的谱之间存在紧密的联系,特别地,对连通图来说,M(G)≤ρ(G)等号成立当且仅当G是一棵树[41].
1983年Gutman和Harary在[50]中定义图的独立集多项式如下：这里α(G,k)为G的具有k个顶点的独立集的数目.为了研究方便,我们定义α(G,0)=1.另外,α(G,1)=|V(G)|为图G的顶点数目.显然,α=(G,k)=0如果k>n.Fisher, Brown得到了图的独立集多项式的根的一些性质(见[9],[34]),Alavi, Malde, Schwenk, Mandrecu和Erdos在[3],[83]中得到了它的系数的一些性质.
1971年,日本化学家Haruo Hosoya介绍了一个关于有机物分子结构图的一个结构描述的参数[58],此参数就是分子结构图对应的匹配多项式的系数之和,即被后来的研究工作者称为Hosoya指数,并记为Z(G)Hosoya等人指出Z(G)与饱和链烃的许多物化性质有密切的联系,尤其是,饱和链烃的沸点与此参数有很高的相关性.Hosoya和他的研究团队研究表明指数Z(G)还可以用来描述特定电子的能级,在[83]中尝试了参数Z(G)在其它领域中的应用Hosoya指数除了在数学、化学中量化某些分子结构的相关数量关系外,近年来在刻画关于图的Hosoya指数的极图方面也取得了很多重要成果(见[120],[44],[61],[9],[51],[37],[22],[96]-[98],[25]).Hosoya指数与一个图的邻接矩阵的特征值有高度的联系(见[37]),并且和图的顶点的度、2-度等图的其它结构参数有关[61].匹配多项式、Hosoya指数、Merrifield-Simmons指数与图的其它指数如Wiener指数[110]也有相互的联系.
美国化学家Richard E. Merrifield和Howard E. Simmons在上个世纪80年代提出了一个通过在有限集上定义一个拓扑参数来描述分子结构的理论,此参数后来被I. Gutman、F. Harary[50]称为Merrifield-Simmons指数,即图的独立集多项式的系数之和,记为σ(G),此参数与物质的其它一些性质密切相关(见[89]-[92]).
Balasubramanian在[6]中利用匹配多项式的根和图的谱研究分子的共振能量.分别是分子结构所对应图的谱和匹配根多项式的根,gj,hj分别表示分子结构的第j层的占有数和相关结构数.因此,关于图的两类多项式和对应的的结构参数在物理、化学、生物等领域有广泛的应用.
本文第一章介绍了图论基本概念,特殊图类的记号和我们研究的主要内容.第二章主要研究了路,圈等几类特殊图类的匹配多项式之间相互整除关系,因为根据图的删除一顶点或者一边的匹配多项式的计算公式(性质4,P.7)任何图的匹配多项式总可以表示成路的匹配多项式的组合形式,因此这些图的匹配多项式与路的匹配多项式之间的关系在比较多项式的最大匹配根,刻画匹配唯一,独立唯一等方面有重要的应用.同时,我们也研究了单圈图、二部图、割边数给定的图和连通度给定的简单图类的最大匹配根并刻画了相应的极图,最后第2.8节刻画了恰有6个不同匹配根的所有图和几类新的匹配等价图,匹配唯一图.
第三章我们给出了独立集多项式前四项系数的表达式,研究了路、圈等图类的独立集多项式多项式性质,给出了独立集多项式最小根关于图的独立数等参数的一个上界,并且比较了一些图类的独立集多项式的对应系数的大小,最后给出了一种构造同独立集多项式的图的一种方法.
我们知道任何图的Hosoya指数满足,Z(Sn)≤Z(G)≤Z(Pn)=fn+1,这里Sn和Pn分别表示具有n个顶点的星图和路,而对于Merrifield-Simmons指数来说,不等号方向恰恰相反并且σ(R)=fn+2,这里fn为第n个斐波那契数.第四章我们主要研究了这两个指数在图的结构变化下相应的变化情况,对于某些图类,如匹配数给定的简单图,割边数给定的简单图,一致圈链等图的两个指数的变化情况并按照相应指数的大小进行了排序.最后在第五章我们给出圈链的匹配多项式,独立集多项式的递推表达式,以及某些特殊项的系数的表达式.
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.
Cvetkovic, Doob, Gutman, Torgasev等人在[18][CH.4.]定义一个图的匹配多项式为：这里m(G,k)为G的k-匹配的数目,匹配多项式MG(x)的根为θ1,θ2,…,θs,并称θ1为最大匹配根,记为M(G).在统计物理学中最初由Heilman和Lieb[62]提出和研究,并由Kunz [72], Gruber等人进一步研究它的相关性质在物理学中的应用.匹配多项式常常可以用某种特殊构造的图的矩阵的特征多项式来表示,如Godsil和Gutman [40],Yan[121]等,因此图的匹配多项式的根和图的谱之间存在紧密的联系,特别地,对连通图来说,M(G)≤ρ(G)等号成立当且仅当G是一棵树[41].
1983年Gutman和Harary在[50]中定义图的独立集多项式如下：这里α(G,k)为G的具有k个顶点的独立集的数目.为了研究方便,我们定义α(G,0)=1.另外,α(G,1)=|V(G)|为图G的顶点数目.显然,α=(G,k)=0如果k>n.Fisher, Brown得到了图的独立集多项式的根的一些性质(见[9],[34]),Alavi, Malde, Schwenk, Mandrecu和Erdos在[3],[83]中得到了它的系数的一些性质.
1971年,日本化学家Haruo Hosoya介绍了一个关于有机物分子结构图的一个结构描述的参数[58],此参数就是分子结构图对应的匹配多项式的系数之和,即被后来的研究工作者称为Hosoya指数,并记为Z(G)Hosoya等人指出Z(G)与饱和链烃的许多物化性质有密切的联系,尤其是,饱和链烃的沸点与此参数有很高的相关性.Hosoya和他的研究团队研究表明指数Z(G)还可以用来描述特定电子的能级,在[83]中尝试了参数Z(G)在其它领域中的应用Hosoya指数除了在数学、化学中量化某些分子结构的相关数量关系外,近年来在刻画关于图的Hosoya指数的极图方面也取得了很多重要成果(见[120],[44],[61],[9],[51],[37],[22],[96]-[98],[25]).Hosoya指数与一个图的邻接矩阵的特征值有高度的联系(见[37]),并且和图的顶点的度、2-度等图的其它结构参数有关[61].匹配多项式、Hosoya指数、Merrifield-Simmons指数与图的其它指数如Wiener指数[110]也有相互的联系.
美国化学家Richard E. Merrifield和Howard E. Simmons在上个世纪80年代提出了一个通过在有限集上定义一个拓扑参数来描述分子结构的理论,此参数后来被I. Gutman、F. Harary[50]称为Merrifield-Simmons指数,即图的独立集多项式的系数之和,记为σ(G),此参数与物质的其它一些性质密切相关(见[89]-[92]).
Balasubramanian在[6]中利用匹配多项式的根和图的谱研究分子的共振能量.分别是分子结构所对应图的谱和匹配根多项式的根,gj,hj分别表示分子结构的第j层的占有数和相关结构数.因此,关于图的两类多项式和对应的的结构参数在物理、化学、生物等领域有广泛的应用.
本文第一章介绍了图论基本概念,特殊图类的记号和我们研究的主要内容.第二章主要研究了路,圈等几类特殊图类的匹配多项式之间相互整除关系,因为根据图的删除一顶点或者一边的匹配多项式的计算公式(性质4,P.7)任何图的匹配多项式总可以表示成路的匹配多项式的组合形式,因此这些图的匹配多项式与路的匹配多项式之间的关系在比较多项式的最大匹配根,刻画匹配唯一,独立唯一等方面有重要的应用.同时,我们也研究了单圈图、二部图、割边数给定的图和连通度给定的简单图类的最大匹配根并刻画了相应的极图,最后第2.8节刻画了恰有6个不同匹配根的所有图和几类新的匹配等价图,匹配唯一图.
第三章我们给出了独立集多项式前四项系数的表达式,研究了路、圈等图类的独立集多项式多项式性质,给出了独立集多项式最小根关于图的独立数等参数的一个上界,并且比较了一些图类的独立集多项式的对应系数的大小,最后给出了一种构造同独立集多项式的图的一种方法.
我们知道任何图的Hosoya指数满足,Z(Sn)≤Z(G)≤Z(Pn)=fn+1,这里Sn和Pn分别表示具有n个顶点的星图和路,而对于Merrifield-Simmons指数来说,不等号方向恰恰相反并且σ(R)=fn+2,这里fn为第n个斐波那契数.第四章我们主要研究了这两个指数在图的结构变化下相应的变化情况,对于某些图类,如匹配数给定的简单图,割边数给定的简单图,一致圈链等图的两个指数的变化情况并按照相应指数的大小进行了排序.最后在第五章我们给出圈链的匹配多项式,独立集多项式的递推表达式,以及某些特殊项的系数的表达式.
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.
引文
[1]J. Aihara, A new defintion of Dewar-type resonance energy,J. Amer. Chem. Soc.,98 (1976) 2750-2758.
[2]J. L. Arocha, Propriedades del polinomio independiente de un grafo, Revista Ciencias Matematicas,5 (1984) 103-110.
[3]Y. Alavi, P. J.Malde, A, J. Schwenk, P. Erdos, The vertex independence se-quence of a graph is not constrained, Congressus Numeranlium,58 (1987) 15-23.
[4]H. Bian, F. J. Zhang, G. P. Wang, H. Z. Yu, Mathing polynomial for chains of cycles, Discrete Mathematics,311 (2011) 319-323.
[5]N. Biggs, Algebraic graph theory (second edition), Cambridge university press, (1993).
[6]K. Balasubramanian, Spectra of matching plynomials, Chemical Physics Let-ters,208 (1993) 219-224.
[7]S. Beraha, J. Kahane, N. Weiss, Limits of zeros of recursively defined families of polynomials, Studies in Foundations and Combinatorics:Advances in Math., Supplementary studies, vol 1. G. Rota (Ed.), Academic Press, New York, (1978).
[8]R. A. Beezer, E. J. Farrell, The matching polynomial of a regular graph, Dis-crete Mathematics,137 (1995) 7-18.
[9]J. I. Brown, C. A. Hickman, R. J. Nowakovski, On the location of roots of independence polynomials, Journal of Algebraic Combinatorics,19 (2004) 273-282.
[10]R. Beezer, E. J. Farrell, Counting sub graphs of a regular graphs, Discrere Mathematics Workshop University of Washington, Tacoma October 14,2006.
[11]J. I. Brown, R.J. Nowakovski, Average independence polynomials, Journal of Combinatorial Thery B,93 (2005) 313-318.
[12]J. I. Brown, K. Dilcher, R. J. Nowakowski, Roots of indenpendence poly-nomials of well-covered graphs, Journal of Algebraic Combinatorics,11 (2000) 197-201.
[13]J. I. Brown, R. J. Nowakowrski, Bounding the roots of independence polyno-mials, Ars Combinatoria 58 (2001) 113-120.
[14]J. Brown and R. Hoshino, On circulants uinquely characterized by their in-dependent polynomials, to appear in Ars Combinatoria.
[15]V. Bruyere, H. Melot, Fibonacci index and stablity number of graphs, A poly-hedral study,J. Comb. Opt., (2009) to appear.
[16]D. Cvetkovic, P. Rowlinson and S. Simic, An introduction to the Theory of Graph Spectra, Chambridge University Press Cambridge. New York. Mel-bourne. Madrid. Cape Town. Sigapore. Sao Oaulo. Delhi. (2010).
[17]D. Cvetkovic, P. Rowlinson, The largest eigenvalue of a graph, A survey, Linear and multilinear algebra,28 (1990) 3-33.
[18]D. Cvetkovic, M. Doob, I. Gutman, A. Torgasev, Recent results in the the-ory of graph spectra, North-Holland-Amsterdam, New York, Oxford, Tokyo. (1988).
[19]D. Cvetkovic, M. Doob, I. Gutman, On graphs whose Spectral radius does not exceed (2+(?)5)1/2, Ars Combinaloria,14(1982) 225-239.
[20]D. Cvetkovic, M. Doob, Sachs, Spectra of graphs-Theory and applications, Deutscher Verlag der Wissenschaften Berlin,1980; Academic Press, New York,1980.
[21]Y. Chen, S. Wen, On the total number of matchings of trees with prescribed diameter. Int. J. Nonlinear Sci.,4(1) (2007) 37-43.
[22]IT. Y. Deng, The Hosoya index in (n,n+1) graphs,J. Math. Chem.,43 (2008) 119-131.
[23]F. M. Dong, A new expression for matching polynomials, Discrete Mathemat-ics,312 (2010) 803-807.
[24]A. Dobrnin, R. Entringer, I. Gutman, Wiener index of trees:Theory and Ap-plications, Acta Applicandae Mathematicae,66 (2001) 211-149.
[25]H. Deng and S. Chen, The extremal unicyclic graphs with respect to Hosoya index and Merrifield-Simmons index, MATCH Commun. Math. Comput. Chem.,59(1) (2008) 171-190.
[26]H. Deng, The largest Hosoya index of (n,n+1) graphs, Comput. Math. Appl., 56(10) (2008) 2499-2506.
[27]H. Deng, The smallest Hosoya index in (n,n+1) graphs,J. Math. Chem.,43(1) (2008) 119-133.
[28]H. Deng, The smallest Merrifield-Simmons index in (n,n+1) graphs, Math. Comput. Modelling,49(1-2) (2009) 320-326.
[29]T. Doslic, F. Mal(?)y, Chain hexagonal cacti:Matchings and independent sets, Discrete Math.,310 (2010) 1676-1690.
[30]E. J. Farrell, An introduction to matching polynomial.J Combin,Theory B,27 (1979) 75-86.
[31]E. J. Farell, J. M. Guo and G. M. Constanine, On the matching coefficients, Descrete Math.,172 (1997) 203-210.
[32]E. J. Farrell, J. M. Guo, Circuit characterizations of nearly of regular graphs, MATCH,25 (1990) 115-130.
[33]E. J. Farrell, J. M. Guo, On the characterizing properties of matching polyno-mials, JCMCC,24 (1997) 193-200.
[34]D. C. Fisher, A. E. Solow, Dependence polynomials, Discrete Mathematics,82 (1990) 251-258.
[35]A. Finbow, B. Hartnell, R. J. Nowakowski, A characterization of well-covered graphs of girth 5 or greater, journal of combinatorial Theory B,57 (1993) 44-68.
[36]B. Furtula et. al, Computer search for trees with minimal ABC index. Applied Mathematics and Computation,219 (2012) 767-772.
[37]M. Fischermann, I. Gutman, A. Hoffman, D. Rautenbach, D. Vidovic, and L, Volkmann, Extremal chemical tree, Z. Naturforsch,57 (2002) 49-52.
[38]E. Ghorbani, Graphs with few matching roots, arxiv:1011.0284v1 [math.col 1 nov 2010:1-10.
[39]C. D. Godsil, Algebraic Combinatorics. New York, London, Chapman and Hall, (1993).
[40]C. D. Godsil and I. Gutman, On the matching polynomials of a graph, Al-gebraic Methods in Graph Theory, Vol.Ⅰ,Ⅱ(Szeged.1978), Colloq. Math. Soc. Janos Bolyai, Vol.25, North-Holland, Amsterdam, New York,(1981) 241-249.
[41]C. D. Godsil, Algebraic matching Theory,Th2 electronic journal of commbina-torics,2 (1995), R5.
[42]C. D. Godsil, I. Gutman, On the theory of the matching polynomial,J. Graph Theory,5 (1981) 137-144.
[43]M. Goldwurm, M. Santini, Clique polynomial have a unique root of smallest modulus, Information Processing Letters,75 (2000) 127-132.
[44]A. Graovac, O. E. Polanksy, On Hermitian matrices associated with match-ing polynomials of graphs,MATCH Commun. Math. Comput. Chem.,21 (1986) 81-91.
[45]I. Gutman, Acylic system with extremal Huckel π-electron energy, Theor. Chim. Acta,45 (1977) 79-87.
[46]I. Gutman, The acylic polynomial of a graph, Publ. Inst. Math.,22 (36) (1977) 63-69.
[47]I. Gutman, The energy of a graph. Ber. Math-staust. Sekt. Forsch. Graz., Ber., 22 (1978)100-105.
[48]I. Gutman, H. Hosoya, On the calculation of the acylic polynomial, Theoret. Chim. Acta.,48 (1978) 279-286.
[49]I. Gutman, Contribution to the spectral theory of trees (Serbo-Groatian), Doct. thesis, Univ. Beograd, El. tehn. fak., (1981).
[50]I. Gutman, F. Harary, Generalizations of the matching polynomials, Utititas Mathematica,24 (1983) 97-106.
[51]I. Gutman, Extremal Hexagonal chains, J. Math. Chem.,12(1-4)(1993) 197-210. Applied graph theory and discrete mathematics in chemistry (Saskatoon, SK,1991).
[52]I. Gutman, O. E. Polansky, Topological Concepts In Organic Chemistry, Springer, Berlin, (1986).
[53]I. Gutman, F. Zhang, On the ordering of graphs with respect to their match-ing numbers, Discrete Applied Mathematics,15 (1986) 25-33.
[54]I. Gutman, Z. Markovic, S. Markovic, A simple method for the approximate calculation of hosoya's index, Chemical physical letters,134 (2) (1987) 139-142.
[55]I. Gutman, A note on analogies between the characteristic and the matching polynomial of a graph, Publications de L'institut Mathematique, Nou velle serie, tome 31(45) (1982) 27-31.
[56]H. Hua, Hosoya index of unicyclic graphs with prescribed pendent vertices, J. Math. Chem.,43 (2) (2008) 831-844.
[57]Y. Hou, On acyclic systems with minimal Hosoya Index, Disceret Applied Mathematics,119 (2002) 251-257.
[58]H. Hosoya, Topological index, A newly proposed quantity characterizing the topological nature of structural isomers of satuated hydrocarbons, Bull. Chem. So. Jpn.,44 (1971) 2332-2339.
[59]D. G. Horrocks, The number of dependent k-sets in a graph is log concave, Journal of Cobinatorial Theory,Series B,84 (2002) 180-185.
[60]C. Henberger, S. Wagner, Maximizing the number of independent subsets over trees with bounded degree, Journal of Graph Theory,58(1) (2008) 49-68.
[61]C. Hoede, X. Li, Clique polynomials and independent set polynomials of graphs, Discrete Mathematics,125 (1994) 219-228.
[62]O. J. Heilmann, E. H. Leib, Monomers and dimers,Phys Rev Letter,24 (1970) 1412-1414.
[63]O. J. Heilmann, E. J. Leib, Theory of monomers-dimer system, Commn. Math. Phys.,25 (1972) 190-232.
[64]H. Hosoya, The topological index Z before and after 1971, Intenet electronic journal of molecular design,1 (2002) 428-442.
[65]H. Haijiabolhassan, M. L. Mehrabadi, On clique polynomials, Australasian Journal of Combinatorial,18 (1998) 313-316.
[66]Y. Hong, Bounds of eigenvalues of graphs, Discr. Math,123 (1993) 65-74.
[67]Y. Hong and J. L. Shu, A sharp upper bound for the spectral radius of the Nordhaus-Gaddum type. Discrete Mathematics,211 (2000) 229-223.
[68]Y. O. Hamidoune, On the number of independent k-set in a claw-free graph, Journal of Combinatorial Theory, Series B,50 (1990) 241-244.
[69]A. Ilic, D. Stevanovie, The Estrada index of chemical trees,J. Math. Chem., Doi 10.1007/s 10910-009-9570-0.
[70]D. J. Klein, M. Randic, Resistance distance,J. Math. Chem.,12 (1993) 81-95.
[71]A. Knopf ma cher, R. F. Tichy, S. Wagner, V. Ziegler, Graphs, partitons and Fibonacci numbers, Discrete Appl. Math.,10 (2007) 1175-1187.
[72]C. Y. Ku, W. Chen, An analogue of the Gallai-Edmonds structure theorem for non-zero roots of the matching polynomial,J. Combin. Theory Ser. B,100 (2010)119-127.
[73]J. Keilson, H. Gerber, Some results for discrete unimodality, Journal of Amer-tican Statistic Association,334 (1971) 386-389.
[74]H. Kunz, Location of the partition function for some classical lattice system, Phys Letter A,32 (1970) 311-312.
[75]柳泊濂,组合矩阵论,科学出版社,北京,2005.
[76]L. Lovasz, M. Plummer, Matching theory, Annals of Discrete Mathematics, North-Holland, New York. (1986).
[77]李改杨,几类图的匹配唯一性,应用数学,2(5)(1992)53-59.
[78]H. Q. Liu, X. Yan, On the Merrifield-Simmons Indices of trees with a pre-scribed diameter, MATCH Commu. Math. Comput. Chem.,57 (2007) 371-384.
[79]H. Liu, X. Yan, Z. Yan, On the Merrifield-Simmons indices and Hosoya in-dices of trees with a prescribed diameter, MATCH Commun. Math. Comput. Chem.,57 (2) (2007) 371-384.
[80]X. Li, H. Zhao, I. Gutman, On the Merrifield-Simmons index of trees, MATCH. Commun. Math. Comput. Chem.,54 (1) (2005) 195-208.
[81]R. Li, An upper bound for the Hosoya index of trees, Applied Mathematical Sciences,24 (2009) 1171-1176.
[82]S. B. Lin, C. Lin, Trees and forest with large and small independent indices, Chinese J. Math.,23 (3) (1995) 199-210.
[83]V. E. Levit, E. Mandrecu, On well-covered trees with unimodal indepen-dence polynomials, Congressus Numerantium,159 (2002) 193-202.-
[84]V. E. Levit, K. Dilcher, R. J. Nowakovski, Roots of independent polynomials of very well covered graphs, Journal of Algebraic Combinatorics,11 (2000) 197-210.
[85]V. E. Levit, E. Mandrescu, Well-covered trees, Congressus Numerantium,139 (1999) 101-112.
[86]X. Li and Z. Zhu, The number of independent sets in unicyclic graphs with a given diameter, Discrete Appl. Math.,157 (7) (2009) 1387-1395.
[87]马海成,两种度序列图的匹配等价图类,数学研究,33(2)(2000)218-221.
[88]马海成,两类图的匹配等价图类,数学研究,2(2002)218-222.
[89]R. E. Merrifield, H. E. Simmons, The structure of molecular toplogical spaces, Theor. Chim. Acta,55 (1980) 55-75.
[90]R. E. Merrifield, H. E. Simmons, The Enumeration of structure-sensitive graphical subsets, Ther. Proc. Natl. Acad. Sci. USA,78 (1981) 692-695.
[91]R. E. Merrifield, H. E. Simmons, Topology of bounding in π-electron sys-tems, Proc. Natl. Acad. Sci. USA,82 (1985) 1-3.
[92]R. E. Merrifield, H. E. Simmons, Topology Methods in Chemistry, Wiley, New York, (1989).
[93]H. Minc, Nonnegative matrices, John Wiley and Sons, New York,1988.
[94]H. C. Ma, H. X. Zhao, The matching unique graphs with largest degree or small degree, Journal of mathematial research and exposition, (24) 2 (2003) 369-373.
[95]V. Nikiforov, Walks and the spectral radius of a graphs, Linear algebra and its applications,418 (2006) 257-268.
[96]J. Ou, On extremal unicyclic molecular graphs with prescribed girth and minimal Hosoya index,J. Math. Chem.,42 (3) (2007) 423-432.
[97]J. Ou, On extremal acylic molecular graphs with maximal Hosoya index, energy, and short diameter,J. Math. Chem.,43 (1) (2008) 328-337.
[98]J. Ou, On extremal acylic molecular graphs with minimal Hosoya index, Dis-crete Appl. Math.,157 (2) (2009) 391-397.
[101]A. S. Pedersen and P. D. Vestergaard, Bounds on the number of vertex in-dependent set in a tree, Ars Combin.,84 (2007) 85-96.
[100]A. S. Pedersen, P. D. Vestergaard, An upper bound on the number of inde-pendend sets in a tree, Ars Combin.,84 (2007) 85-96.
[101]A. S. Pedersen, P. D. Vestergaard, Bounds on the number of independent set in a graph, Taiwanese J. Math.,84 (2006) 1575-1587.
[102]X. F. Pan, J. M. Xu, C. Yang, M. J. Zhou, Some graphs with mumimum Hosoya index and maximum Merrifield-Simmons index, MATCH Commun. Math. Comput. Chem.,57 (1) (2007) 235-242.
[103]H. Prodinger, R. F. Tichy, Fibonacci numbers of gtaphs, Fibonacci Quart.,20 (1)(1982)16-21.
[104]G. Ravindra, Well-covered graphs,J. Combin. Inform. Sci.,2 (1977) 20-21.
[105]申世昌,T形树的匹配唯一性,数学研究,1(32)(1999)86-91.
[106]R. Stanley, A bound on the spectral radius of graphs with e edges, Linear Algebra and its Applications,87 (1987) 267-269.
[107]申世昌,左光纪,一类树的匹配唯一性,青海师范大学学报,4(1999)9-13.
[108]D. Stevanovic, Bounding the largest eigenvalue of tree in terms of the largest vertex degree, Linear Algebra Appl.360 (2003) 35-42.
[109]A. J. Schwenk, On unimodal sequence of graphic invariants, Hournal of Combinatorial Theory B,30 (1981) 247-250.
[110]W. G. Yan, Y. Y. N. Ye, Connections between Wiener index and matchings, Journal of Mathematical Chemistry,2 (39) (2006) 389-398.
[111]吴振奎,斐波那契数列,辽宁教育出版社,(1987).
[112]T. M. Westerberg, K. J. Dawson, K. W. Mclaughlin, The Hosoya index, Lucas number, and QSPR, Endeavor,1 (2005) 1-15.
[113]W. G. Yan, Y. N. Ye, On the matching polynomial of subdivision graphs, Discrete Applied Mathematics, to appear.
[114]S. A. Wahid, On the matching polynomial of graphs, M. Sc. thesis, Univ. West Indies, St. Augustine (Trinidad),1983.
[115]G. Wagner, Extremal trees with respect to Hosoya Index and Merrifield-Simmons Index, MATCH Commun. Math. Comput.Chem.,57 (1)(2007) 221-223.
[116]B. Wang, C. Ye and H. Zhao, Extremal unicyclic graphs with respect to Merrifield-Simmons index, MACTH Commun. Math. Comput. Chem.,59 (1) (2008) 203-216.
[117]X. X. Wang, X. F. Guo, On the orderring of a class of graphs with respect to their matching numbers, Journal of Mathematical Chemistry,42 (2007) 473-480.
[118]A. Yu, X. Lv, The Merrifield-Simmons indices and Hosoya Indices of trees with k pendant vertices, J. Math. Chem.,41(1) (2007) 33-43.
[119]Z. Yan, H. Liu and H. Liu, The maximum Merrifield-Simmons indices and minimal Hosoya indices of unicyclic graphs, MATCH Commun. Math. Com-put. Chem.,59 (1) (2008) 157-170.
[120]A. Yu, F. Tian, A king of graphs with minimal Hosoya index and Max-imial Merrifield-Simmons index, MATCH Commun. Math. Comput. Chem.,55 (2006)103-118.
[121]W. Yan, Y.-N. Yeh, F. J. Zhang, On the matching polynomials of graphs with small number of cycles of even length, Int. J. Quantum Chem.,105 (2005) 124-130.
[122]W. Yan, Y.-N. Yeh, On the matching polynomial of subdivision graphs, Discrete Applied Mathematics, to appear.
[123]张海良,图Pm∪Q(3,n)的匹配等价图,江西师范大学学报,31(6)(2007)607-610.
[124]L. Z. Zhang, The proof of Gutman's congecture concering extremal hexag-onal chains,J. Systems. Sci. Math. Sci.,18 (4) (1998) 460-465.
[125]张海良,吴丹霞,饱和链烃的Hosoya旨数与其分子结构图的匹配多项式及根,大学数学,27(4)(2012)23-28.
[126]H. L. Zhang, The exactly divide ability of several matching polynomials of graphs and the matching equivalent graphs of certain graph, Pure And Applied Mathematics,23 (2) (2007) 178-182.
[127]H. L. Zhang, On the roots of the matching polnomial of graphs and charac-terize the matching equicalent graphs of two kinds of graphs, Master thesis, (2004).
[128]H. X. Zhao, R. Y. Liu, On the character of the matching polynomial and its application to circuit characterization of graphs, JCMCC,37 (2001) 75-86.
[129]H. Zhao, X. Li, On the Fibonacci numbers of trees. Fibonacci Quart.,44 (1) (2006) 32-38.
[130]H. X. Zhao, R. Liu, On the Merrifield-Simmons indices of graphs, MATCH Commun. Math. Comput. Chem.,56 (3) (2006) 617-624.
[131]H. X. Zhao, X. L. Li and R. Y. Liu, On the minimum real root of the adjoint polynomial of a graph, to appear.
[132]H. X. Zhao, B. F. Huo and R. Y. Liu, Chromaticity of the complements of paths, Journal of mathematical study,23 (4) (2000) 345-353.
[133]T. Zaslavsky, Complementary matching vectors and the uniform matching extension property, European J. Combin.,2 (1981) 91-103.
[2]J. L. Arocha, Propriedades del polinomio independiente de un grafo, Revista Ciencias Matematicas,5 (1984) 103-110.
[3]Y. Alavi, P. J.Malde, A, J. Schwenk, P. Erdos, The vertex independence se-quence of a graph is not constrained, Congressus Numeranlium,58 (1987) 15-23.
[4]H. Bian, F. J. Zhang, G. P. Wang, H. Z. Yu, Mathing polynomial for chains of cycles, Discrete Mathematics,311 (2011) 319-323.
[5]N. Biggs, Algebraic graph theory (second edition), Cambridge university press, (1993).
[6]K. Balasubramanian, Spectra of matching plynomials, Chemical Physics Let-ters,208 (1993) 219-224.
[7]S. Beraha, J. Kahane, N. Weiss, Limits of zeros of recursively defined families of polynomials, Studies in Foundations and Combinatorics:Advances in Math., Supplementary studies, vol 1. G. Rota (Ed.), Academic Press, New York, (1978).
[8]R. A. Beezer, E. J. Farrell, The matching polynomial of a regular graph, Dis-crete Mathematics,137 (1995) 7-18.
[9]J. I. Brown, C. A. Hickman, R. J. Nowakovski, On the location of roots of independence polynomials, Journal of Algebraic Combinatorics,19 (2004) 273-282.
[10]R. Beezer, E. J. Farrell, Counting sub graphs of a regular graphs, Discrere Mathematics Workshop University of Washington, Tacoma October 14,2006.
[11]J. I. Brown, R.J. Nowakovski, Average independence polynomials, Journal of Combinatorial Thery B,93 (2005) 313-318.
[12]J. I. Brown, K. Dilcher, R. J. Nowakowski, Roots of indenpendence poly-nomials of well-covered graphs, Journal of Algebraic Combinatorics,11 (2000) 197-201.
[13]J. I. Brown, R. J. Nowakowrski, Bounding the roots of independence polyno-mials, Ars Combinatoria 58 (2001) 113-120.
[14]J. Brown and R. Hoshino, On circulants uinquely characterized by their in-dependent polynomials, to appear in Ars Combinatoria.
[15]V. Bruyere, H. Melot, Fibonacci index and stablity number of graphs, A poly-hedral study,J. Comb. Opt., (2009) to appear.
[16]D. Cvetkovic, P. Rowlinson and S. Simic, An introduction to the Theory of Graph Spectra, Chambridge University Press Cambridge. New York. Mel-bourne. Madrid. Cape Town. Sigapore. Sao Oaulo. Delhi. (2010).
[17]D. Cvetkovic, P. Rowlinson, The largest eigenvalue of a graph, A survey, Linear and multilinear algebra,28 (1990) 3-33.
[18]D. Cvetkovic, M. Doob, I. Gutman, A. Torgasev, Recent results in the the-ory of graph spectra, North-Holland-Amsterdam, New York, Oxford, Tokyo. (1988).
[19]D. Cvetkovic, M. Doob, I. Gutman, On graphs whose Spectral radius does not exceed (2+(?)5)1/2, Ars Combinaloria,14(1982) 225-239.
[20]D. Cvetkovic, M. Doob, Sachs, Spectra of graphs-Theory and applications, Deutscher Verlag der Wissenschaften Berlin,1980; Academic Press, New York,1980.
[21]Y. Chen, S. Wen, On the total number of matchings of trees with prescribed diameter. Int. J. Nonlinear Sci.,4(1) (2007) 37-43.
[22]IT. Y. Deng, The Hosoya index in (n,n+1) graphs,J. Math. Chem.,43 (2008) 119-131.
[23]F. M. Dong, A new expression for matching polynomials, Discrete Mathemat-ics,312 (2010) 803-807.
[24]A. Dobrnin, R. Entringer, I. Gutman, Wiener index of trees:Theory and Ap-plications, Acta Applicandae Mathematicae,66 (2001) 211-149.
[25]H. Deng and S. Chen, The extremal unicyclic graphs with respect to Hosoya index and Merrifield-Simmons index, MATCH Commun. Math. Comput. Chem.,59(1) (2008) 171-190.
[26]H. Deng, The largest Hosoya index of (n,n+1) graphs, Comput. Math. Appl., 56(10) (2008) 2499-2506.
[27]H. Deng, The smallest Hosoya index in (n,n+1) graphs,J. Math. Chem.,43(1) (2008) 119-133.
[28]H. Deng, The smallest Merrifield-Simmons index in (n,n+1) graphs, Math. Comput. Modelling,49(1-2) (2009) 320-326.
[29]T. Doslic, F. Mal(?)y, Chain hexagonal cacti:Matchings and independent sets, Discrete Math.,310 (2010) 1676-1690.
[30]E. J. Farrell, An introduction to matching polynomial.J Combin,Theory B,27 (1979) 75-86.
[31]E. J. Farell, J. M. Guo and G. M. Constanine, On the matching coefficients, Descrete Math.,172 (1997) 203-210.
[32]E. J. Farrell, J. M. Guo, Circuit characterizations of nearly of regular graphs, MATCH,25 (1990) 115-130.
[33]E. J. Farrell, J. M. Guo, On the characterizing properties of matching polyno-mials, JCMCC,24 (1997) 193-200.
[34]D. C. Fisher, A. E. Solow, Dependence polynomials, Discrete Mathematics,82 (1990) 251-258.
[35]A. Finbow, B. Hartnell, R. J. Nowakowski, A characterization of well-covered graphs of girth 5 or greater, journal of combinatorial Theory B,57 (1993) 44-68.
[36]B. Furtula et. al, Computer search for trees with minimal ABC index. Applied Mathematics and Computation,219 (2012) 767-772.
[37]M. Fischermann, I. Gutman, A. Hoffman, D. Rautenbach, D. Vidovic, and L, Volkmann, Extremal chemical tree, Z. Naturforsch,57 (2002) 49-52.
[38]E. Ghorbani, Graphs with few matching roots, arxiv:1011.0284v1 [math.col 1 nov 2010:1-10.
[39]C. D. Godsil, Algebraic Combinatorics. New York, London, Chapman and Hall, (1993).
[40]C. D. Godsil and I. Gutman, On the matching polynomials of a graph, Al-gebraic Methods in Graph Theory, Vol.Ⅰ,Ⅱ(Szeged.1978), Colloq. Math. Soc. Janos Bolyai, Vol.25, North-Holland, Amsterdam, New York,(1981) 241-249.
[41]C. D. Godsil, Algebraic matching Theory,Th2 electronic journal of commbina-torics,2 (1995), R5.
[42]C. D. Godsil, I. Gutman, On the theory of the matching polynomial,J. Graph Theory,5 (1981) 137-144.
[43]M. Goldwurm, M. Santini, Clique polynomial have a unique root of smallest modulus, Information Processing Letters,75 (2000) 127-132.
[44]A. Graovac, O. E. Polanksy, On Hermitian matrices associated with match-ing polynomials of graphs,MATCH Commun. Math. Comput. Chem.,21 (1986) 81-91.
[45]I. Gutman, Acylic system with extremal Huckel π-electron energy, Theor. Chim. Acta,45 (1977) 79-87.
[46]I. Gutman, The acylic polynomial of a graph, Publ. Inst. Math.,22 (36) (1977) 63-69.
[47]I. Gutman, The energy of a graph. Ber. Math-staust. Sekt. Forsch. Graz., Ber., 22 (1978)100-105.
[48]I. Gutman, H. Hosoya, On the calculation of the acylic polynomial, Theoret. Chim. Acta.,48 (1978) 279-286.
[49]I. Gutman, Contribution to the spectral theory of trees (Serbo-Groatian), Doct. thesis, Univ. Beograd, El. tehn. fak., (1981).
[50]I. Gutman, F. Harary, Generalizations of the matching polynomials, Utititas Mathematica,24 (1983) 97-106.
[51]I. Gutman, Extremal Hexagonal chains, J. Math. Chem.,12(1-4)(1993) 197-210. Applied graph theory and discrete mathematics in chemistry (Saskatoon, SK,1991).
[52]I. Gutman, O. E. Polansky, Topological Concepts In Organic Chemistry, Springer, Berlin, (1986).
[53]I. Gutman, F. Zhang, On the ordering of graphs with respect to their match-ing numbers, Discrete Applied Mathematics,15 (1986) 25-33.
[54]I. Gutman, Z. Markovic, S. Markovic, A simple method for the approximate calculation of hosoya's index, Chemical physical letters,134 (2) (1987) 139-142.
[55]I. Gutman, A note on analogies between the characteristic and the matching polynomial of a graph, Publications de L'institut Mathematique, Nou velle serie, tome 31(45) (1982) 27-31.
[56]H. Hua, Hosoya index of unicyclic graphs with prescribed pendent vertices, J. Math. Chem.,43 (2) (2008) 831-844.
[57]Y. Hou, On acyclic systems with minimal Hosoya Index, Disceret Applied Mathematics,119 (2002) 251-257.
[58]H. Hosoya, Topological index, A newly proposed quantity characterizing the topological nature of structural isomers of satuated hydrocarbons, Bull. Chem. So. Jpn.,44 (1971) 2332-2339.
[59]D. G. Horrocks, The number of dependent k-sets in a graph is log concave, Journal of Cobinatorial Theory,Series B,84 (2002) 180-185.
[60]C. Henberger, S. Wagner, Maximizing the number of independent subsets over trees with bounded degree, Journal of Graph Theory,58(1) (2008) 49-68.
[61]C. Hoede, X. Li, Clique polynomials and independent set polynomials of graphs, Discrete Mathematics,125 (1994) 219-228.
[62]O. J. Heilmann, E. H. Leib, Monomers and dimers,Phys Rev Letter,24 (1970) 1412-1414.
[63]O. J. Heilmann, E. J. Leib, Theory of monomers-dimer system, Commn. Math. Phys.,25 (1972) 190-232.
[64]H. Hosoya, The topological index Z before and after 1971, Intenet electronic journal of molecular design,1 (2002) 428-442.
[65]H. Haijiabolhassan, M. L. Mehrabadi, On clique polynomials, Australasian Journal of Combinatorial,18 (1998) 313-316.
[66]Y. Hong, Bounds of eigenvalues of graphs, Discr. Math,123 (1993) 65-74.
[67]Y. Hong and J. L. Shu, A sharp upper bound for the spectral radius of the Nordhaus-Gaddum type. Discrete Mathematics,211 (2000) 229-223.
[68]Y. O. Hamidoune, On the number of independent k-set in a claw-free graph, Journal of Combinatorial Theory, Series B,50 (1990) 241-244.
[69]A. Ilic, D. Stevanovie, The Estrada index of chemical trees,J. Math. Chem., Doi 10.1007/s 10910-009-9570-0.
[70]D. J. Klein, M. Randic, Resistance distance,J. Math. Chem.,12 (1993) 81-95.
[71]A. Knopf ma cher, R. F. Tichy, S. Wagner, V. Ziegler, Graphs, partitons and Fibonacci numbers, Discrete Appl. Math.,10 (2007) 1175-1187.
[72]C. Y. Ku, W. Chen, An analogue of the Gallai-Edmonds structure theorem for non-zero roots of the matching polynomial,J. Combin. Theory Ser. B,100 (2010)119-127.
[73]J. Keilson, H. Gerber, Some results for discrete unimodality, Journal of Amer-tican Statistic Association,334 (1971) 386-389.
[74]H. Kunz, Location of the partition function for some classical lattice system, Phys Letter A,32 (1970) 311-312.
[75]柳泊濂,组合矩阵论,科学出版社,北京,2005.
[76]L. Lovasz, M. Plummer, Matching theory, Annals of Discrete Mathematics, North-Holland, New York. (1986).
[77]李改杨,几类图的匹配唯一性,应用数学,2(5)(1992)53-59.
[78]H. Q. Liu, X. Yan, On the Merrifield-Simmons Indices of trees with a pre-scribed diameter, MATCH Commu. Math. Comput. Chem.,57 (2007) 371-384.
[79]H. Liu, X. Yan, Z. Yan, On the Merrifield-Simmons indices and Hosoya in-dices of trees with a prescribed diameter, MATCH Commun. Math. Comput. Chem.,57 (2) (2007) 371-384.
[80]X. Li, H. Zhao, I. Gutman, On the Merrifield-Simmons index of trees, MATCH. Commun. Math. Comput. Chem.,54 (1) (2005) 195-208.
[81]R. Li, An upper bound for the Hosoya index of trees, Applied Mathematical Sciences,24 (2009) 1171-1176.
[82]S. B. Lin, C. Lin, Trees and forest with large and small independent indices, Chinese J. Math.,23 (3) (1995) 199-210.
[83]V. E. Levit, E. Mandrecu, On well-covered trees with unimodal indepen-dence polynomials, Congressus Numerantium,159 (2002) 193-202.-
[84]V. E. Levit, K. Dilcher, R. J. Nowakovski, Roots of independent polynomials of very well covered graphs, Journal of Algebraic Combinatorics,11 (2000) 197-210.
[85]V. E. Levit, E. Mandrescu, Well-covered trees, Congressus Numerantium,139 (1999) 101-112.
[86]X. Li and Z. Zhu, The number of independent sets in unicyclic graphs with a given diameter, Discrete Appl. Math.,157 (7) (2009) 1387-1395.
[87]马海成,两种度序列图的匹配等价图类,数学研究,33(2)(2000)218-221.
[88]马海成,两类图的匹配等价图类,数学研究,2(2002)218-222.
[89]R. E. Merrifield, H. E. Simmons, The structure of molecular toplogical spaces, Theor. Chim. Acta,55 (1980) 55-75.
[90]R. E. Merrifield, H. E. Simmons, The Enumeration of structure-sensitive graphical subsets, Ther. Proc. Natl. Acad. Sci. USA,78 (1981) 692-695.
[91]R. E. Merrifield, H. E. Simmons, Topology of bounding in π-electron sys-tems, Proc. Natl. Acad. Sci. USA,82 (1985) 1-3.
[92]R. E. Merrifield, H. E. Simmons, Topology Methods in Chemistry, Wiley, New York, (1989).
[93]H. Minc, Nonnegative matrices, John Wiley and Sons, New York,1988.
[94]H. C. Ma, H. X. Zhao, The matching unique graphs with largest degree or small degree, Journal of mathematial research and exposition, (24) 2 (2003) 369-373.
[95]V. Nikiforov, Walks and the spectral radius of a graphs, Linear algebra and its applications,418 (2006) 257-268.
[96]J. Ou, On extremal unicyclic molecular graphs with prescribed girth and minimal Hosoya index,J. Math. Chem.,42 (3) (2007) 423-432.
[97]J. Ou, On extremal acylic molecular graphs with maximal Hosoya index, energy, and short diameter,J. Math. Chem.,43 (1) (2008) 328-337.
[98]J. Ou, On extremal acylic molecular graphs with minimal Hosoya index, Dis-crete Appl. Math.,157 (2) (2009) 391-397.
[101]A. S. Pedersen and P. D. Vestergaard, Bounds on the number of vertex in-dependent set in a tree, Ars Combin.,84 (2007) 85-96.
[100]A. S. Pedersen, P. D. Vestergaard, An upper bound on the number of inde-pendend sets in a tree, Ars Combin.,84 (2007) 85-96.
[101]A. S. Pedersen, P. D. Vestergaard, Bounds on the number of independent set in a graph, Taiwanese J. Math.,84 (2006) 1575-1587.
[102]X. F. Pan, J. M. Xu, C. Yang, M. J. Zhou, Some graphs with mumimum Hosoya index and maximum Merrifield-Simmons index, MATCH Commun. Math. Comput. Chem.,57 (1) (2007) 235-242.
[103]H. Prodinger, R. F. Tichy, Fibonacci numbers of gtaphs, Fibonacci Quart.,20 (1)(1982)16-21.
[104]G. Ravindra, Well-covered graphs,J. Combin. Inform. Sci.,2 (1977) 20-21.
[105]申世昌,T形树的匹配唯一性,数学研究,1(32)(1999)86-91.
[106]R. Stanley, A bound on the spectral radius of graphs with e edges, Linear Algebra and its Applications,87 (1987) 267-269.
[107]申世昌,左光纪,一类树的匹配唯一性,青海师范大学学报,4(1999)9-13.
[108]D. Stevanovic, Bounding the largest eigenvalue of tree in terms of the largest vertex degree, Linear Algebra Appl.360 (2003) 35-42.
[109]A. J. Schwenk, On unimodal sequence of graphic invariants, Hournal of Combinatorial Theory B,30 (1981) 247-250.
[110]W. G. Yan, Y. Y. N. Ye, Connections between Wiener index and matchings, Journal of Mathematical Chemistry,2 (39) (2006) 389-398.
[111]吴振奎,斐波那契数列,辽宁教育出版社,(1987).
[112]T. M. Westerberg, K. J. Dawson, K. W. Mclaughlin, The Hosoya index, Lucas number, and QSPR, Endeavor,1 (2005) 1-15.
[113]W. G. Yan, Y. N. Ye, On the matching polynomial of subdivision graphs, Discrete Applied Mathematics, to appear.
[114]S. A. Wahid, On the matching polynomial of graphs, M. Sc. thesis, Univ. West Indies, St. Augustine (Trinidad),1983.
[115]G. Wagner, Extremal trees with respect to Hosoya Index and Merrifield-Simmons Index, MATCH Commun. Math. Comput.Chem.,57 (1)(2007) 221-223.
[116]B. Wang, C. Ye and H. Zhao, Extremal unicyclic graphs with respect to Merrifield-Simmons index, MACTH Commun. Math. Comput. Chem.,59 (1) (2008) 203-216.
[117]X. X. Wang, X. F. Guo, On the orderring of a class of graphs with respect to their matching numbers, Journal of Mathematical Chemistry,42 (2007) 473-480.
[118]A. Yu, X. Lv, The Merrifield-Simmons indices and Hosoya Indices of trees with k pendant vertices, J. Math. Chem.,41(1) (2007) 33-43.
[119]Z. Yan, H. Liu and H. Liu, The maximum Merrifield-Simmons indices and minimal Hosoya indices of unicyclic graphs, MATCH Commun. Math. Com-put. Chem.,59 (1) (2008) 157-170.
[120]A. Yu, F. Tian, A king of graphs with minimal Hosoya index and Max-imial Merrifield-Simmons index, MATCH Commun. Math. Comput. Chem.,55 (2006)103-118.
[121]W. Yan, Y.-N. Yeh, F. J. Zhang, On the matching polynomials of graphs with small number of cycles of even length, Int. J. Quantum Chem.,105 (2005) 124-130.
[122]W. Yan, Y.-N. Yeh, On the matching polynomial of subdivision graphs, Discrete Applied Mathematics, to appear.
[123]张海良,图Pm∪Q(3,n)的匹配等价图,江西师范大学学报,31(6)(2007)607-610.
[124]L. Z. Zhang, The proof of Gutman's congecture concering extremal hexag-onal chains,J. Systems. Sci. Math. Sci.,18 (4) (1998) 460-465.
[125]张海良,吴丹霞,饱和链烃的Hosoya旨数与其分子结构图的匹配多项式及根,大学数学,27(4)(2012)23-28.
[126]H. L. Zhang, The exactly divide ability of several matching polynomials of graphs and the matching equivalent graphs of certain graph, Pure And Applied Mathematics,23 (2) (2007) 178-182.
[127]H. L. Zhang, On the roots of the matching polnomial of graphs and charac-terize the matching equicalent graphs of two kinds of graphs, Master thesis, (2004).
[128]H. X. Zhao, R. Y. Liu, On the character of the matching polynomial and its application to circuit characterization of graphs, JCMCC,37 (2001) 75-86.
[129]H. Zhao, X. Li, On the Fibonacci numbers of trees. Fibonacci Quart.,44 (1) (2006) 32-38.
[130]H. X. Zhao, R. Liu, On the Merrifield-Simmons indices of graphs, MATCH Commun. Math. Comput. Chem.,56 (3) (2006) 617-624.
[131]H. X. Zhao, X. L. Li and R. Y. Liu, On the minimum real root of the adjoint polynomial of a graph, to appear.
[132]H. X. Zhao, B. F. Huo and R. Y. Liu, Chromaticity of the complements of paths, Journal of mathematical study,23 (4) (2000) 345-353.
[133]T. Zaslavsky, Complementary matching vectors and the uniform matching extension property, European J. Combin.,2 (1981) 91-103.