首页 | 本学科首页   官方微博 | 高级检索  
     检索      


Bounds on eigenvalues and chromatic numbers
Authors:Dasong Cao
Institution:

School of Industrial and System Engineering Georgia Institute of Technology Atlanta, Georgia 30332, USA

Abstract:We give new bounds on eigenvalue of graphs which imply some known bounds. In particular, if T(G) is the maximum sum of degrees of vertices adjacent to a vertex in a graph G, the largest eigenvalue ρ(G) of G satisfies View the MathML source with equality if and only if either G is regular or G is bipartite and such that all vertices in the same part have the same degree. Consequently, we prove that the chromatic number of G is at most View the MathML source with equality if and only if G is an odd cycle or a complete graph, which implies Brook's theorem. A generalization of this result is also given.
Keywords:
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号