几类图的谱

【作者】 尹书华；

【导师】 束金龙；

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

【摘要】 本文主要研究简单无向图的谱，包括图的邻接谱和Lapace谱，具体内容如下： 1．给出了图G的Laplace谱半径的一个新上界： μ₁（G）≤(d₁+2d_i-1+（8（i-1）（d₁-d_i）+（d₁-2d_i-1）²）^1/2)/2，其中1≤i≤n，i≠2时等式成立当且仅当G为正则二部图，i=2时等式成立当且仅当G为正则二部图或星图。 2．对树的代数连通度进行了讨论，利用移接变形给出树的代数连通度的一种变化关系，同时给出了两类树的代数连通度与直径的关系。 3．研究了k-连通图G的谱半径的上下界及达到上下界的极图。 4．讨论了双圈图的最大特征值与最小特征值，给出了双圈图的最大特征值达到最大的极图及最小特征值达到最小的极图。更多还原

【Abstract】 In this paper, we mainly study the spectrum of graphs, including the adjacency spectrum and the Laplacian spectrum. Some results will be given in this thesis. 1. We first present a sharp bound for the Laplacian spectral radius as follows:where 1 < i < n. When i = 2 the equality holds if and only if G is a regular bipartite graph, when i = 2 the equality holds if and only if G is a regular bipartite graph or a star graph.2. The algebraic connectivity of trees is determined by the graft transformation, meanwhile the relation between the algebraic connectivity and the diameter of two classes of trees is also determined.3. We also give the upper and low bounds for the spectral raduis of graphs whose vertex connectivity is k.4. Finally, we investigate the largest and smallest eigenvalues of the double cyclic. Moreover, we characterize all extremal graphs with these bounds.更多还原