图的谱极值理论

发布时间：2018-03-25 14:25

本文选题：谱半径　切入点：团数　出处：《上海交通大学》2015年博士论文

【摘要】：图的谱极值理论是极值图论与代数图论相互交叉的一个研究领域.它是图论最近新兴的一个主要研究方向和焦点,其在计算机科学和工程领域有着广泛的应用.本文主要包含三个部分：·首先,第二章中研究给定最大团个数和顶点数的图类中图的完全子图的结构性质,并且刻画在这类图中具有最多团个数的所有极图.这些结论推广并加强了图的Turan定理、Moon定理及Hedman的定理,进而证明图的谱Turan定理.第三章研究图的谱Turan定理的另外一种变形：给定独立数的最小谱半径问题.·其次,研究与化学图论相关的图的谱极值定理.第四章中研究给定最大度的树的Laplacian特征多项式的系数.建立Laplacian特征多项式的系数与图的匹配多项式之间的联系,并刻画给定最大度的树中具有最小匹配多项式的所有极树和具有最小关联能量的所有极树.第五、六章中研究图的距离矩阵与维纳指数之间的联系.采用代数与图论相结合的技巧证明Sills和Wang(Discrete Mathematics),林辉球、洪渊、王建锋和束金龙(Linear algebra and its applications)提出的两个猜想.·最后,第七章中研究弧数给定的简单有向图的最大谱半径.利用矩阵范数的技巧给出了简单有向图的谱半径的可达上界,并且刻画在一定条件下达到最大谱半径的所有简单有向图.
[Abstract]:The theory of spectral extremum of graphs is a research field which intersects extreme graph theory and algebraic graph theory, and it is a main research direction and focus of graph theory. It has been widely used in computer science and engineering. This paper mainly consists of three parts: first, in chapter 2, we study the structural properties of complete subgraphs of graphs with given maximum number of clusters and vertices. And all the polar graphs with the largest number of groups are characterized in this kind of graphs. These results extend and strengthen the Turan's theorem and Hedman's theorem of graphs. In chapter 3, we study another kind of deformation of spectral Turan theorem of graphs: the problem of minimum spectral radius of given independent number. The spectral extremum theorems of graphs related to chemical graph theory are studied. In chapter 4, the coefficients of Laplacian characteristic polynomials of trees with given maximum degree are studied. The relation between the coefficients of Laplacian characteristic polynomials and the matching polynomials of graphs is established. All polar trees with minimal matching polynomials and all polar trees with minimum correlation energy in a tree with a given maximum degree are characterized. In chapter six, we study the relation between distance matrix and Wiener exponent of graphs. We prove two conjectures proposed by Sills and Wang(Discrete Mathematicsl, Lin Huiqiu, Hong Yuan, Wang Jianfeng and Bong Jinlong's Linear algebra and its applications by using the technique of combining algebra and graph theory. In chapter 7, the maximum spectral radius of a simple directed graph with given arc number is studied. By using the technique of matrix norm, the upper bound of the spectral radius of a simple directed graph is given, and all simple digraphs with maximum spectral radius are characterized under certain conditions.
【学位授予单位】：上海交通大学
【学位级别】：博士
【学位授予年份】：2015
【分类号】：O157.5

【相似文献】