Some sharp lower bounds for spectral radius of connected graphs
-
摘要: 讨论连通简单图的谱半径的下界问题. 证明了关于途径数的一个不等式, 进而利用最大、最小度、平均度、2-度和$k$-途径数给出图的谱半径一些新的下界. 再运用相 似矩阵特性与\,Weyl\,不等式, 并利用途径数得到图谱半径的另一下界. 同时刻画了上述下界的全部极值图.
-
关键词:
- 邻接矩阵 /
- 谱半径 /
- Perron 特征向量 /
- 下界
Abstract: This paper studied lower bounds on the spectral radius of connected simple graphs and proved an useful inequality for the number of walks. Furthermore, some new lower bounds on the spectral radius of graphs were provided in terms of the maximum and minimum degree, the average degree, the 2-degree and the number of $k$-walks(with $k$ vertexes). By applying the properties of similar matrices and the Weyl inequalities, another lower bound was obtained by means of the number of $k$-walks. Simultaneously, all extremal graphs which achieve above bounds were also characterized.-
Key words:
- adjacency matrix /
- spectral radius /
- Perron eigenvector /
- lower bound
-
[1] {1} YU A M, LU M, TIAN F. On the spectral radius of graphs[J]. Linear Algebra Appl, 2004, 387: 41-49. {2} NIKIFOROV V. Walks and the spectral radius of graphs[J]. Linear Algebra Appl, 2006, 418: 257-268. {3} HORN R A, JOHNSON C R. Matrix Analysis[M]. Cambridge: Cambridge University Press, 1985. {4} CVETKOVJ\'{C} D, DOOB M, SACHS H. Spectra of Graphs-Theory and Application[M]. New York: Academic Press, 1980. {5} HONG Y. Bounds of eigenvalues of graphs[J]. Discrete Math, 1993, 123: 65-74. {6} DAS K, KUMAR P. Some new bounds on the spectral radius of graphs[J]. Discrete Math, 2004, 281: 149-161. {7} HOFMEISTER M. Spectral radius and degree sequence[J]. Math Nachr, 1988, 139: 37-44. {8} HONG Y, ZHANG X D. Sharp upper and lower bounds for the Laplacian matrices of trees[J]. Discrete Math, 2005, 296: 187-197. {9} HU S B. A sharp lower bound of the spectral radius of simple graphs[J]. Anal Discrete Math, 2009, 3: 379-385. {10} SHI L S. Bounds on the (Laplacian) spectral radius of graphs[J]. Linear Algebra Appl, 2007, 422: 755-770. {11} YU A M. A new upper bound for the laplacian spectral radius of a graph[J]. Electronic Journal of Linear Algebra, 2010, 20: 730-738. -
点击查看大图
计量
- 文章访问数: 2110
- HTML全文浏览量: 23
- PDF下载量: 2204
- 被引次数: 0
下载: