基于归一化拉普拉斯谱的图确定性研究及其第三小特征值的下界表征

《Discrete Mathematics》：On the spectral characterization of graphs with respect to the normalized Laplacian

本文探讨了图谱理论中的一个重要挑战，即由归一化拉普拉斯矩阵 (L) 谱唯一确定的图（L-DS 图）。文章的核心在于，通过刻画所有满足第三小归一化拉普拉斯特征值 ρn-2(G) ≥ n/(n-1) 的连通图，发现了一类新的L-DS图。该研究结果证实了图 Kt2? (Kt1∪ Kt3) 由其归一化拉普拉斯谱唯一确定，这深化了我们对图结构与其谱特性之间复杂关系的理解。

　　

研究工具

在本节中，我们将回顾一些在主要结果证明中将要用到的结论。首先，我们列出关于对称矩阵谱性质的一个经典结果。

引理 2.1[22]

设 B 是一个 n × n 对称矩阵，B_k是其 k × k 阶领先主子矩阵。那么，对于 i = 1, 2, …, k，有 λ_i(B) ≥ λ_i(B_k) ≥ λ_n?k+i(B)。

接下来我们展示关于图的归一化拉普拉斯特征值的几个结果。

引理 2.2[16]

令 G (? K_n) 是一个 n 阶连通图。那么 ρ_n-1≤ 1，等号成立当且仅当 G 是一个（此处省略具体图类名称，原文未提供完整结论，但引理旨在说明特征值的界和对应的结构特征）。

主要结果

在本节中，我们将首先刻画所有阶数为 n 且其第三小归一化拉普拉斯特征值不小于 n/(n-1) 的连通图，这利用了图 G_s•(t₁, t₂, …, t_s) 的谱性质。为此，我们分别给出当 s = 3, 4 时其第三小归一化拉普拉斯特征值的结果。

引理 3.1

令 G ? G₃•(t₁, t₂, t₃) 且 t₁+ t₂+ t₃= n。那么 ρ_n-2(G) ≥ n/(n-1)，等号成立当且仅当 t₂≥ 2。此外，若 t₁≥ t₃，则 ρ_n-2(G₃•(t₁, 1, t₃)) = (t₁+ 1) / t₁。

证明

（此部分内容涉及归一化拉普拉斯矩阵的详细演算，原文未在此处展开具体证明过程，因此翻译时省略计算细节，保留结论性陈述。）归一化拉普拉斯矩阵（的谱分析）是证明的关键。

结论

在本文中，我们刻画了所有阶数为 n 且其第三小归一化拉普拉斯特征值至少为 n/(n-1) 的连通图。作为该结果的一个应用，我们识别出一类 L-DS 图，包括了 P₃（它与 G₃同构）的每个团扩展。这表明第三小归一化拉普拉斯特征值在研究 L-DS 图时扮演着重要角色。我们证明主要结果的方法严重依赖于在刻画……（原文此处句子不完整，但意指依赖于之前介绍的工具和引理）。