几类广义冠图的研究

发布时间：2018-07-01 09:30

本文选题：图谱理论 + 广义冠图　；参考：《兰州理工大学》2017年硕士论文

【摘要】：图谱理论在计算机科学、通信网络、量子化学等众多学科中都有应用,由图的特征多项式可以直接得到图的谱,因此研究得到图的特征多项式对于研究这些学科都很有益。图的邻接矩阵A(G)表示了图中顶点与顶点之间的邻接关系,邻接矩阵的特征多项式称为邻接特征多项式。图的度对角矩阵是对角线上为每个顶点的度的对角矩阵,记为D(G)。Laplacian矩阵记为L(G)=D(G)-A(G),Laplacian矩阵的特征多项式称为Laplacian 特征多项式;signless Laplacian 矩阵记为Q(G)=D(G)+A(G), signless Laplacian矩阵的特征多项式称为signlessLaplacian特征多项式。图的各项特征多项式的特征根及其重数称为图的谱,分别为邻接谱、Laplacian谱和signless Laplacian谱。同谱而又非同构的图称为同谱图,分别为邻接同谱图(记为A-同谱图)、Laplacian同谱图(记为L -同谱图)和signless Laplacian同谱图(记为Q-同谱图)。冠图是通过多个图进行图操作所得到的复杂图,剖分图是在每条边上新添加一个顶点所得到的图。本文将冠图广义化并融合了剖分图操作,构造了两种新的广义冠图:广义剖分冠边图S(G)(?)H,和广义剖分冠点图S(G)(?)Hi。应用分块矩阵、舒尔补、矩阵的冠值等计算并证明了这两类广义冠图的邻接特征多项式、Laplacian特征多项式和signless Laplacian特征多项式。作为应用还得到了在特殊情况下这两种广义冠图的生成树数目和Kirchhoff指数,并给出了计算生成树数目的例子。随后还得到了一系列的邻接同谱图、Laplacian同谱图和signless Laplacian同谱图图簇,并给出了例子。本文的主要成果有:(1)定义了一类新的广义冠图--广义剖分冠边图S(G)(?)Hi。计算并证明了它的各项特征多项式。(2)计算并证明了在图G为r-正则图,图H1,...Hm均为图H时构造的非广义的剖分冠边图S(G)(?)H的L-谱、生成树个数和Kirchhoff指数。并给出了计算生成树数目的例子。(3)得到了一系列邻接同谱、Laplacian同谱和signless Laplacian同谱的广义剖分冠边图图簇,并给出了同谱图的例子。(4)定义了一类新的广义冠图--广义剖分冠点图S(G)(?)Hi。计算并证明了它的各项i特征多项式。(5)计算并证明了在图G为r-正则图,图H1,...Hn均为图H时构造的非广义的剖分冠点图S(G)(?)的L-谱、生成树个数和Kirchhoff指数。并给出了计算生成树数目的例子。(6)得到了一系列邻接同谱、Laplacian同谱和signless Laplacian 同谱的广义剖分冠点图图簇,并给出了同谱图的例子。
[Abstract]:The graph theory has been applied in many subjects such as computer science, communication network, quantum chemistry and so on. The spectrum of graphs can be obtained directly from the characteristic polynomials of graphs, so it is very useful to study the characteristic polynomials of graphs. The adjacency matrix A (G) of a graph represents the adjacency between vertices and vertices in a graph. The characteristic polynomial of the adjacency matrix is called the adjacent characteristic polynomial. The degree diagonal matrix of a graph is a diagonal matrix with a degree of each vertex on the diagonal line. The characteristic polynomial denoted by D (G). Laplacian matrix is called the signless Laplacian matrix, which is called the signless Laplacian matrix. The characteristic polynomial of the G) A (G), signless Laplacian matrix is called the signlessLaplacian characteristic polynomial. The eigenvalues and their multiplicity of characteristic polynomials of graphs are called the spectrum of graphs, which are adjacent spectrum and signless spectrum, respectively. Graphs with the same spectrum but not isomorphism are called isospectral graphs, which are adjacent isospectral graphs (referred to as A- isospectral graphs) and signless Laplacian isospectral graphs (referred to as Q-isospectral graphs), respectively. A crown graph is a complex graph which is obtained by the operation of multiple graphs, and a subdivision graph is a graph obtained by adding a new vertex to each edge. In this paper, two new generalized crown graphs are constructed: s (G) (?) H, S (G) (?) H and S (G) (?) Hi. By using block matrix, Schulm complement and the crown value of matrix, it is proved that the adjacent characteristic polynomials of these two classes of generalized crown graphs are Laplacian characteristic polynomials and signless Laplacian characteristic polynomials. As applications, the number of spanning trees and Kirchhoff exponents of these two generalized crown graphs are obtained, and an example is given to calculate the number of spanning trees. A series of adjacent Laplacian isospectral graphs and signless Laplacian isospectral graphs are obtained, and an example is given. The main results of this paper are as follows: (1) A new generalized crown graph S (G) (?) Hi. Its characteristic polynomials are calculated and proved. (2) the L- spectrum, the number of spanning trees and the Kirchhoff exponent of the non-generalized dissecting crown edge graph S (G) (?) H are calculated and proved when the graph G is r-regular and the graph H _ 1 路H _ m is a graph H. An example is given to calculate the number of spanning trees. (3) A series of generalized dissected crown edge graphs with adjacent isospectral and signless isospectral graphs are obtained. (4) A new class of generalized crown graphs S (G) (?) is defined. The various I characteristic polynomials of the graph are calculated and proved. (5) the graph S (G) (?) constructed when the graph G is r-regular and the graph H _ 1 路H _ n is all graph H. The number of spanning trees and Kirchhoff exponent. An example of calculating the number of spanning trees is given. (6) A series of generalized subdivision crown graph families adjacent to the isospectral Laplacian and signless Laplacian isospectrum are obtained, and an example of the isospectral graph is given.
【学位授予单位】：兰州理工大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：O157.5;TP391.41

【参考文献】