Extrema of graph eigenvalues
Extrema of graph eigenvalues
复制标题
图特征值的极值
DOI：
10.1016/j.laa.2015.05.016
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
V. Nikiforov
中科院分区：
文献类型：
--
作者：
V. Nikiforov
1993年，Hong提出了n阶图G的第k个最大特征值λ k（G）的最佳界的问题。对于任意2<k2，这一难题从未得到解决< n. In the present paper tight bounds are obtained for all k>，而对于第k个最大奇异值λ k ∈（G），得到了更严格的界.其中一些界限是基于泰勒的强正则图，和其他的Kharaghani的方法，用于构建阿达玛矩阵。同样的构造也可以应用于其他的开放问题，比如Nordhaus-Gaddum问题：λ k（G）+ λ k（G <$）能有多大？这些构造在另一个公开问题上也是成功的：Ky Fan范数λ 1 <$（G）+<$+ λ k <$（G）能有多大？图的Ky Fan范数推广了图的能量概念，因此这个问题推广了最大能量图的问题。在最后一节中，重新陈述了（-1，1）-矩阵的几个结果和问题，这似乎为此类研究提供了比图更自然的基础。本文中的许多结果都与开放性问题和有待进一步研究的问题配对。
In 1993 Hong asked what are the best bounds on the k'th largest eigenvalue λ k (G) of a graph G of order n. This challenging question has never been tackled for any 2< k< n. In the present paper tight bounds are obtained for all k> 2, and even tighter bounds are obtained for the k'th largest singular value λ k⁎(G). Some of these bounds are based on Taylor's strongly regular graphs, and others on a method of Kharaghani for constructing Hadamard matrices. The same kind of constructions are applied to other open problems, like Nordhaus–Gaddum problems of the kind: How large can λ k (G)+ λ k (G¯) be? These constructions are successful also in another open question: How large can the Ky Fan norm λ 1⁎(G)+⋯+ λ k⁎(G) be? Ky Fan norms of graphs generalize the concept of graph energy, so this question generalizes the problem for maximum energy graphs. In the final section, several results and problems are restated for (− 1, 1)-matrices, which seem to provide a more natural ground for such research than graphs. Many of the results in the paper are paired with open questions and problems for further study.