【作者】 张海良；

【导师】 束金龙；

【作者基本信息】 华东师范大学 ， 运筹学与控制论， 2013， 博士

【摘要】 设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个斐波那契数.第四章我们主要研究了这两个指数在图的结构变化下相应的变化情况,对于某些图类,如匹配数给定的简单图,割边数给定的简单图,一致圈链等图的两个指数的变化情况并按照相应指数的大小进行了排序.最后在第五章我们给出圈链的匹配多项式,独立集多项式的递推表达式,以及某些特殊项的系数的表达式.更多还原

【Abstract】 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.更多还原