连通性、生成树打包数与无符号拉普拉斯谱半径

《Linear Algebra and its Applications》：Connectivity, spanning tree packing number and signless Laplacian spectral radius

　　

摘要
图 G 的点连通度（分别或边连通度）是指移除后使图变为非连通图的最小顶点数（分别或边数）。图 G 的生成树打包数 ???(??) 是 G 中包含的最大边不相交生成树的数量。在本文中，我们首先证明了在所有阶为 n、最小度为 δ 且点连通度为 k 的图中，?????(????????1 ∪???????+1) 是具有最大无符号拉普拉斯谱半径的唯一极图。我们还研究了边连通度的类似问题。此外，我们提供了一个无符号拉普拉斯谱半径条件以保证 ???(??) ≥??。最后，我们在文末提出了一个问题。

引言
本文中考虑的所有图都是简单、有限且无向的。设 G 为一个图，顶点集为 ???(??)，边集为 ???(??)。G 的邻接矩阵写作 ???(??)= (????,??)??,??∈??，其中若 ????? ∈???(??) 则 ????,??= 1，否则为 0。设 ???? := ?????(??) 表示 ???(??) 的第 i 个最大特征值，??= 1,2,?,??。特别地，我们将 ??1?(??) 称为 G 的邻接谱半径。设 ???(??)= diag?(???(??):??∈???(??)) 表示 G 的顶点点度对角矩阵。那么 ???(??)= ???(??)+???(??) 称为 G 的无符号拉普拉斯矩阵。???(??) 的最大特征值，记为 ?????(??)，称为 G 的无符号拉普拉斯谱半径。

图 G 的点连通度，记为 ???(??)，是移除后使图变为非连通图的最小顶点数。特别地，若 ???(??) ≥??，则称 G 是 k-连通的。从特征值角度研究点连通度在图论中有丰富的历史。1973 年，Fiedler [6] 证明了对于最小度为 δ 的非完全图 G，有 ???(??) ≥??? ??2?(??)。 (??,??,??)-图定义为具有 n 个顶点，是 d-正则的，且 ??= max2≤??≤???|????| 的图。Krivelevich 和 Sudakov [12] 表明，对于满足 ?? ≤??/2 的任何 (??,??,??)-图 G，有 ???(??) ≥??? 36???2/??。Brouwer 和 Koolen [2] 表明距离正则图的点连通度等于其度。后来，Li 等人 [13] 刻画了图 ?????(??1 ∪????????1)，该图在所有点连通度为 k 的图中取得最大邻接谱半径，其中 G?H 表示从不相交并 ?? ∪?? 中通过添加图 G 和 H 之间所有可能的边得到的图。这一结果在 [15] 中得到扩展，将最小度作为参数引入。受 [15] 中工作的启发，在本文中，我们将考虑图的点连通度与无符号拉普拉斯谱半径之间的关系。

定理 1
设 G 为阶为 n 的连通图，最小度为 δ，点连通度 ???(??)= ??。那么
?????(??)≤?????(?????(????????1∪???????+1))，
等号成立当且仅当 ?? ??????(????????1 ∪???????+1)。

图 G 的边连通度，记为 ??′?(??)，是移除后使图变为非连通图的最小边数。2010 年，Cioab? [3] 研究了 d-正则图的边连通度与邻接特征值之间的关系，并表明若 ?? ≥?? ≥2 且 ??2?(??)< ???(???1)???(??+1)?(??????1)，则 ??′?(??) ≥??。随后，Liu 等人 [16] 将 [3] 中的结果扩展到一般图，即对于最小度为 δ 的图 G，若 ??2?(??)< ???(???1)???(??+1)?(??????1)，则 ??′?(??) ≥??。关于 ??′?(??) 和 ??2?(??) 联系的更多相关结果，感兴趣的读者可参考 [9]、[14]、[17] 及其中的参考文献。记 ??????,??+1 为通过在不相交团 ????+1 和 ????????1 之间添加 k 条边得到的图的集合。2018 年，Ning 等人 [18] 证明了具有固定最小度 δ 和边连通度 k 的 n-顶点图的最大邻接谱半径是在 ??????,??+1 中取得的。此外，对于 0 ≤?? ≤3，Ning 等人 [18] 确定 ??????,??+1 是 ??????,??+1 中具有最大邻接谱半径的唯一极图，其中 ??????,??+1 是由 ????+1 ∪????????1 通过添加 k 条边连接 ????+1 中的一个顶点和 ????????1 中的 k 个顶点得到的图，他们提出了以下猜想。

猜想 1 参见 [18]
对于 4 ≤??< ??，??????,??+1 是阶为 n、最小度为 δ 且边连通度为 k 的所有图中谱半径最大的图。

最近，Fan、Gu 和 Lin [7] 证实了这一猜想，对于 ?? ≥2???+ 4 成立。作为一个基本图性质，边连通度满足 ??′ ≤??。该不等式成立是因为移除与最小度顶点关联的所有边将断开图。在本文中，我们将通过其无符号拉普拉斯谱半径研究边连通度。

定理 2
设 G 为阶为 n 的图，最小度为 δ，边连通度 ??′?(??)= ??，其中 ?? ≥??2+ 4???+ 3。
(i) 若 0 ≤?? ≤??? 1 且 G 是具有最大无符号拉普拉斯谱半径的图，则 ?? ∈??????,??+1。
(ii) 若 ??= ??，则 ?????(??) ≤?????(??????,1)，等号成立当且仅当 ?? ???????,1。

图 G 的生成树打包数，记为 ???(??)，是 G 中包含的最大边不相交生成树的数量。2010 年，Seymour [5] 提出了一个关于确定 ???(??) 与图 G 的特征值之间关系的问题。Cioab6 和 Wong [5] 部分回答了这个问题，证明了对于 d-正则图 G，若 ?? ≥2??? ≥4 且 ??2?(??)< ???2?(2????1)??+1，则 ???(??) ≥??。在同一篇论文中，他们进一步猜想充分条件可以改善为 ??2?(??)< ???2????1??+1，并针对 ??= 2,3 完成了该猜想的初步工作。后来，Gu 等人 [9] 将其扩展到一般图，并猜想对于一般图 G，若 ?? ≥2??? ≥4 且 ??2?(??)< ???2????1??+1，则 ???(??) ≥??。这一猜想最终在 [16] 中得到解决。此外，Cioab? 等人 [4] 通过构造极图表明 [16] 中的界本质上是最佳的。最近，Fan、Gu 和 Lin [7] 通过图的邻接谱半径研究了连通图 G 的 ???(??)。受 [7] 中结果的启发，我们将在下面给出无符号拉普拉斯谱版本。

定理 3
设 G 为阶 ?? ≥2???+ 3 且 ?? ≥2 的连通图。若
?????(??)≥?????(?????1?(??1∪???????))，
则 ???(??) ≥??，除非 ?? ??????1?(??1 ∪???????)。

章节片段
预备知识
我们首先介绍商矩阵的概念，这是谱图论中的一个重要工具。设 B 为一个实 ?? ×?? 矩阵，且 ??= {1,2,…,??}= [1,??]。给定一个划分 Π :??= ?1∪?2∪?∪???，矩阵 B 可以相应地划分为
??=?? ? ? ? ? ? ????1,1??1,2???1,????2,1??2,2???2,??????????,1????,2?????,???? ? ? ? ? ? ??。
B 关于 Π 的商矩阵定义为 ?? ×?? 矩阵 ??Π= (????,??)????,??=1，其中 ????,?? 是 ????,?? 所有行和的平均值。若矩阵 M 的每个块 ????,?? 的常数性质...（原文截断）

主要结果的证明
对于任何 ?? ∈???(??)，设 ???(??) 表示 v 的邻域集合，且 ?????(??)= |???(??)| （或简写为 ???(??)）称为 v 在 G 中的度。现在我们可以给出定理 1、2 和 3 的证明。

定理 1 的证明
假设 G 是所有阶为 n、固定最小度为 δ 且点连通度为 k 的图中具有最大无符号拉普拉斯谱半径的图。由于 ???(??)= ??，根据引理 2，我们得到 ??< ??+???12，因此 ?? ≥2???? ??+ 2。根据点连通度的定义，存在一些非空...（原文截断）

结论性评论
在定理 2 中，我们证明了具有最小度 δ 和边连通度 k 的 n-顶点图的最大无符号拉普拉斯谱半径是在 ??????,??+1 中取得的，其中 ?? ≤??? 1。探索 ??????,??+1 中具有最大无符号拉普拉斯谱半径的极图是自然的。我们提出以下问题。

问题 1
对于 0 ≤?? ≤??? 1，具有最小度 δ 和边连通度 k 的 n 顶点图的最大无符号拉普拉斯谱半径是多少？回想一下，??????,?? 是由...（原文截断）

致谢
我们要向匿名审稿人表示极大的感谢，他们提出的宝贵建议大大提高了本文的质量。Yanhua Zhao 得到了中国国家自然科学基金（编号：12401452）和江苏省基础研究计划（编号：BK20240833）的资助。Dandan Fan 得到了中国国家自然科学基金（编号：12301454）的资助。

Yanhua Zhao|HaZhe Ye|Dandan Fan