图拟拉普拉斯矩阵的最大特征值.pdf

22 5 V ol. 22. N o . 5 2006 10 JO U RAL O F YA N BEI N O RM AL U N IV ERSIT Y Oct . 2006 刘学娟, 许三星 ( 北京科技大学数学系, 北京 100083) 图谱理论是图论研究的重要理论之一, G = ( V , E) 为有限无向简 图, A ( G) 和 D( G ) 分别表示 G 的邻接矩阵和度对角矩阵. Q( G) = D( G) + A ( G) 称为图G 的拟拉普拉斯矩阵, 它是图谱理论的研究对象. 本 文利用G 的顶点数, 边数, 最大度, 最小度以及非负矩阵理论给出Q( G) 的最大特征值的新的界值估计. 简 图 拟拉普拉斯矩阵 特征值 O 157. 5 A 1009 - 1939( 2006) 05- 00 18- 03 G = ( V, E) n , , Q ( G) V ( G) = { , , L, } , E ( G) = { e , , . 1 2 n 1 e , L, e } , n 1, m 0. d( ) 2 m i i 1 相关知识及引理 , d . A ( G) , D( G) = diag( d ( ) , d ( ) , i 1 2 L, d ( )) G . [ 1] n 1 X , r (X ) X i L ( G) = D ( G) - A ( G) G i . r (X) i , i , Q ( G) = D ( G) + A ( G) G X , c (X) X i . i , Q ( G) () c (X) i , X . i , , L n 1 2 R (X ) = x r 0. G [ 1] i ij j n j = 1 ,