圈图谱半径问题研究

发布时间：2018-06-20 01:51

本文选题：单圈图 + 双圈图　；参考：《辽宁工业大学》2016年硕士论文

【摘要】：图论是组合数学的一个重要分支,它在量子信息、量子计算、量子化学、计算机存储图的信息等方面起到了极大地作用,并在一定程度上推动了它们的发展。本文主要讨论了单圈图和双圈图的谱半径问题。在研究圈图谱理论及应用方面,洪渊等人首先研究了图与图的特征值之间的关系,给出了n阶单圈图的谱半径的可达上(下)界。本文研究圈图的邻接谱半径的问题,首先讨论了围长为g且有k个悬挂点的单圈图的极图及其上界,并对此类图进行谱半径排序。通过移接变形的方法及匹配的相关理论得到该类图的谱半径的极图;利用特征多项式的性质以及点的度与二度的关系确定了该类图的谱半径的上界为1+(n-2)~1/2。其次,将该方法加以推广,通过嫁接、缩边等运算方法,并结合特征值计算的技巧,讨论给定割点数的单圈图与其谱半径的关系,给出了此类单圈图中具有第三大邻接谱半径的图类的结构。进一步对双圈图的邻接谱半径进行研究。已有的文献已经得到了双圈图的前五大邻接谱半径相应的图类,本文在此基础上加以扩展,通过对双圈图进行收缩,嫁接等运算,利用特征多项式的性质,针对树图与双圈图所处的位置关系不同,分四种情况进行讨论,得到了双圈图中第六大和第七大的谱半径及其对应的图类。图的谱问题的研究是图论中比较重要的一类,本文研究的圈图谱半径问题中所采用的方法在其他图形的谱半径问题上有着比较广泛的应用。
[Abstract]:Graph theory is an important branch of combinatorial mathematics. It plays a great role in quantum information, quantum computation, quantum chemistry and computer storage of graph information, and promotes their development to a certain extent. In this paper, we mainly discuss the spectral radius of unicyclic graphs and bicyclic graphs. In the study of circle graph theory and application, Hong Yuan et al first studied the relation between graph and eigenvalue of graph, and gave the upper (lower) bound of spectral radius of n-order unicyclic graph. In this paper, we study the problem of the adjacent spectral radius of a cycle graph. Firstly, we discuss the pole graph and its upper bound of a unicyclic graph with g girth and k hanging points, and sort the spectral radius of this kind of graph. The pole graph of spectral radius of this kind of graph is obtained by means of the method of shifting deformation and the theory of matching, and the upper bound of spectral radius of this kind of graph is determined to be 1 / 2 / 2 by using the properties of characteristic polynomial and the relation between the degree of point and the second degree. Secondly, the method is extended to discuss the relationship between the monocyclic graph of a given cut point and its spectral radius by grafting, shrinking edge, and combining the technique of eigenvalue calculation. The structure of graphs with the third largest adjacent spectral radius in this kind of unicyclic graphs is given. Furthermore, the radius of the adjacent spectrum of bicyclic graphs is studied. The previous literatures have obtained the graph classes corresponding to the first five adjacent spectral radii of bicyclic graphs. On this basis, this paper extends them by using the properties of characteristic polynomials through the contraction and grafting operations of bicyclic graphs. The sixth and seventh largest spectral radii and their corresponding classes of bicyclic graphs are obtained by discussing the different positions of tree graphs and bicyclic graphs in four cases. The study of the spectrum problem of graphs is an important class in graph theory. The method used in the circle map radius problem studied in this paper has been widely used in the spectral radius problem of other graphs.
【学位授予单位】：辽宁工业大学
【学位级别】：硕士
【学位授予年份】：2016
【分类号】：O157.5

【相似文献】