不含星森林的给定大小图的谱极值

《Discrete Applied Mathematics》：Spectral extrema of graphs with fixed size and without star forests

　　

摘要

设 $G(m, H)$ 为边数为 $m$ 的 $H$-自由图的集合。著名的 Brualdi-Hoffman-Turán 型问题探讨的是：$G(m, H)$ 中图的最大谱半径是多少？近年来，该问题引起了广泛关注。设 $S_l$ 表示 $l+1$ 个顶点的星形图。(Wang 和 Zhang, 2026) 证明了，对于 $k \geq 1$ 和足够大的 $m$，若 $G \in G(m, \bigcup_{i=1}^{k+1} S_{\ell_i})$，则 $\lambda(G) \leq k - 1 + \sqrt{4m - k^2} + \frac{1}{2}$，等号成立当且仅当 $G \cong K_k \vee \frac{m-k}{k-1/2} K_1$。注意，该结果中的极值图仅在 $m + \frac{k(k+1)}{2} \equiv 0 \pmod{k}$ 时才有良好定义。因此，在条件 $m + \frac{k(k+1)}{2} \equiv l \pmod{k}$（其中 $1 \leq l \leq k-1$）下确定 $G(m, \bigcup_{i=1}^{k+1} S_{\ell_i})$ 中图的最大谱半径是自然而然的，也是有趣的。在本文中，我们解决了这一问题，并刻画了对应的极值图。我们还提出了一个一般性研究问题。

引言

本文所讨论的所有图均为有限的、无向的、简单的（即不含环或多重边）。除非另有说明，否则我们采用 Bondy-Murty [1] 和 Godsil-Royle [12] 等标准参考文献中确立的图论传统符号和术语。

若一个图不含 $H$ 作为子图，则称该图为 $H$-自由图。$H$ 的 Turán 数 $ex(n, H)$ 是 $n$ 个顶点的 $H$-自由图的最大边数。经典的 Turán 型问题要求确定 Turán 数 $ex(n, H)$。图 Turán 数的研究是极值图论的中心课题之一。详情可参阅综述 [10]、[22]。

我们注意到，在众多研究中，关于星形森林 Turán 数的研究非常丰富。设 $S_l$ 表示 $l+1$ 个顶点的星形图。1959 年，Erd?s 和 Gallai [8] 确定了所有 $n \geq 2k-1$ 且 $k \geq 2$ 时的 $ex(n, kS_1)$，并证明了相应的极值图为 $K_{2k-1} \cup (n-2k+1)K_1$ 或 $K_{k-1} \vee (n-k+1)K_1$。之后，Yuan 和 Zhang [26] 完全确定了所有 $n$ 下的 $ex(n, kS_2)$，并刻画了相应的极值图。2013 年，Lidicky、Liu 和 Palmer [16] 对足够大的 $n$ 获得了 $ex(n, \bigcup_{i=1}^k S_{\ell_i})$，并确定了相应的极值图。最终，Li、Yin 和 Li [13] 完全推导出所有正整数 $k, \ell, n$ 下 $ex(n, kS_\ell)$ 的精确值。

受经典 Turán 型问题的启发，Nikiforov [2]、[20] 发起了谱极值问题的研究，并进行了系统性的调查，这被称为 Brualdi-Solheid-Turán 型问题和 Brualdi–Hoffman–Turán 型问题。

**问题 1 Brualdi-Solheid-Turán 型问题** [20]

给定图 $H$，$n$ 个顶点的 $H$-自由图的最大谱半径是多少？

**问题 2 Brualdi–Hoffman–Turán 型问题** [2]

给定图 $H$，边数为 $m$ 的图的最大谱半径是多少？

事实上，Brualdi-Solheid-Turán 型问题已得到广泛研究。1986 年，Wilf [23] 证明了 $n$ 个顶点的 $K_{r+1}$-自由图 $G$ 的谱半径满足 $\lambda(G) \leq (1 - \frac{1}{r})n$。2007 年，Nikiforov [19] 改进了之前的结果，证明若 $G$ 是阶为 $n$ 且 $r \geq 2$ 的 $K_{r+1}$-自由图，则 $\lambda(G) \leq \lambda(T_r(n))$，等号成立当且仅当 $G = T_r(n)$，其中 $T_r(n)$ 表示 $n$ 个顶点的完全 $r$-部图，其各部大小为 $\lfloor \frac{n}{r} \rfloor$ 或 $\lceil \frac{n}{r} \rceil$。Feng、Yu 和 Zhang [9] 确定了给定阶数下所有 $kS_1$-自由图的最大谱半径，并识别了极值图。2019 年，Chen、Liu 和 Zhang [5] 获得了阶为 $n$ 的 $kS_2$-自由图的最大谱半径，其中 $k \geq 2$ 且 $n \geq 8k^2 - 3k$。相应的极值图也被刻画。之后他们 [6] 解决了阶为 $n$ 的 $(\bigcup_{i=1}^k S_{\ell_i})$-自由图的最大谱半径问题，其中 $k \geq 2$ 且 $\ell_1 \geq \cdots \geq \ell_k \geq 1$。关于 Brualdi-Solheid-Turán 型问题的更多最新进展，可参阅 [4]。

Brualdi–Hoffman–Turán 型问题也得到了深入研究。为简便起见，设 $G(m, F)$ 表示边数为 $m$ 的所有无孤立顶点的 $F$-自由图的集合。Nikiforov [17]、[18] 证明了，对于每个图 $G \in G(m, K_{r+1})$，有 $\lambda(G) \leq \sqrt{2m(1 - \frac{1}{r})}$，等号成立当且仅当 $r = 2$ 时 $G$ 是完全二部图，以及 $r \geq 3$ 时 $G$ 是完全正则 $r$-部图。我们采用如下记号：$F_t = K_1 \vee P_{t-1}$，$F_{k,3} = K_1 \vee kP_2$，以及 $\theta_{1,p,q}$ 是由连接两个顶点的三条内部不相交路径（长度分别为 $1, p, q$）构成的 $\theta$ 图。

以下结果由 Gao 和 Li [11]（$k=2$ 时）和 Li、Zhao 和 Zou [15]（$k \geq 3$ 时）获得，他们确定了 $G(m, F_{2k+2})$ 中图谱半径的紧上界。

**定理 1.1** [11]、[15]

设 $k \geq 2$ 且 $m \geq 94k^6 + 6k^5 + 46k^4 + 56k^3 + 196k^2$。若 $G \in G(m, F_{2k+2})$，则 $\lambda(G) \leq k - 1 + \sqrt{4m - k^2} + \frac{1}{2}$，等号成立当且仅当 $G \cong K_k \vee \frac{m-k}{k} - \frac{1}{2} K_1$。

可以看到 $G(m, C_{2k+1}) \subseteq G(m, \theta_{1,2,2k-1}) \subseteq G(m, F_{2k+1})$，$G(m, C_{2k+2}) \subseteq G(m, \theta_{1,2,2k}) \subseteq G(m, F_{2k+2})$ 且 $G(m, F_{2k+1}) \subseteq G(m, F_{2k+2})$。极值图 $K_k \vee (\frac{m-k}{k} - \frac{1}{2}) K_1$ 不含 $C_{2k+1}$（分别为 $C_{2k+2}$、$\theta_{1,2,2k-1}$、$\theta_{1,2,2k}$、$F_{2k+1}$）。因此，当 $m \geq 94k^6 + 6k^5 + 46k^4 + 56k^3 + 196k^2$ 时，关于 $G(m, C_{2k+1} \cup C_{2k+2})$（分别为 $G(m, \theta_{1,2,2k-1} \cup \theta_{1,2,2k})$）的 Brualdi–Hoffman–Turán 型问题的解（参见 [14]）是定理 1.1 的直接推论。

注意，定理 1.1 中的极值图 $K_k \vee (\frac{m-k}{k} - \frac{1}{2}) K_1$ 仅在 $m + \frac{k(k+1)}{2} \equiv 0 \pmod{k}$ 时才有良好定义。因此，在条件 $m + \frac{k(k+1)}{2} \equiv l \pmod{k}$（其中 $1 \leq l \leq k-1$）下确定 $G \in G(m, F_{2k+2})$ 中具有最大谱半径的图是自然而然的，也是具有挑战性的；更多细节参见 [25]。最近，Chang 等人 [3] 确定了在条件 $m + \frac{k(k+1)}{2} \equiv l \pmod{k}$（其中 $1 \leq l \leq k-1$）下 $G(m, \theta_{1,2,2k}) \cup G(m, \theta_{1,2,2k})$（分别为 $G(m, C_{2k-1}) \cup G(m, C_{2k})$）中具有最大谱半径的图。

值得注意的是，问题 1 在 $H$ 为星形森林且 $n$ 足够大时已得到完全解决。因此，研究星形森林的问题 2 是自然而然的。注意 $kS_1$ 是 $F_{2k}$ 的子图，且 $K_{k-1} \vee (\frac{m-k}{k-1} - \frac{1}{2}) K_1$ 是一个 $kS_1$-自由图。作为定理 1.1 的结果，我们可以立即确定 $G(m, kS_1)$ 中具有最大谱半径的图（当 $m$ 足够大时）；另参见 [14]。最近，Wang 和 Zhang [27] 考虑了沿此方向的一般情况。

**定理 1.2** [27]

对于正整数 $k \geq 1$ 和 $\ell_i \geq 1$（$i \in [k+1]$），设 $G$ 为 $G(m, \bigcup_{i=1}^{k+1} S_{\ell_i})$ 中的图，且 $m \geq (2k+1)^2 (\sum_{i=1}^{k+1} \ell_i + k - 1)^2$。则 $\lambda(G) \leq k - 1 + \sqrt{4m - k^2} + \frac{1}{2}$，等号成立当且仅当 $G = K_k \vee (\frac{m-k}{k} - \frac{1}{2}) K_1$。

考虑到 $K_k \vee (\frac{m-k}{k} - \frac{1}{2}) K_1$ 仅在 $m + \frac{k(k+1)}{2} \equiv 0 \pmod{k}$ 时才有良好定义。受 Chang 等人 [3] 的启发，在定理 1.2 的相同条件下，当 $m + \frac{k(k+1)}{2} \equiv l \pmod{k}$（其中 $1 \leq l \leq k-1$）时，如何确定 $G(m, \bigcup_{i=1}^{k+1} S_{\ell_i})$ 中具有最大谱半径的图，这是一个有趣的问题。在本文中，我们解决了这一问题。此外，还识别了对应的极值图。

我们的主要结果表述如下。

**定理 1.3**

对于正整数 $k \geq 1$ 和 $\ell_i \geq 1$（$i \in [k+1]$），设 $G$ 为 $G(m, \bigcup_{i=1}^{k+1} S_{\ell_i})$ 中的图，且 $m \geq (7k+7)^2 (\sum_{i=1}^{k+1} \ell_i + k - 1)^2$。若 $m + \frac{k(k+1)}{2} \equiv l \pmod{k}$（其中 $1 \leq l \leq k-1$），则 $\lambda(G) \leq \lambda(S_{\frac{m-lk}{k+k}+3/2, k_1, l})$，等号成立当且仅当 $G \cong S_{\frac{m-lk}{k+k}+3/2, k_1, l}$。

**组织结构**

在本节的剩余部分，我们介绍一些记号和基本概念。在第 2 节中，我们给出一些预备结果。在第 3 节中，我们给出定理 1.3 的证明，并刻画了在以下条件下的极值图：$k \geq 1$，$i \in [k+1]$ 时 $\ell_i \geq 1$，$m + \frac{k(k+1)}{2} \equiv l \pmod{k}$（其中 $1 \leq l \leq k-1$）且 $m$ 足够大。最后一节给出了结论性的评论。

**记号和基本概念**

设 $G = (V(G), E(G))$ 为一个图。对于顶点 $v \in V(G)$，设 $N_G(v)$ 表示 $G$ 中与 $v$ 相邻的顶点集。我们用 $\sim$ 表示两个顶点相邻。顶点 $v \in V(G)$ 的度 $d_G(v)$ 是 $N_G(v)$ 中顶点的数量。我们用 $\Delta(G)$ 表示 $G$ 的最大度，即 $\Delta(G) = \max\{d_G(v) : v \in V(G)\}$。

对于两个子集 $R, S \subseteq V(G)$，$e(R, S)$ 表示图中一条端点在 $R$ 中、另一条端点在 $S$ 中的边的数量，特别地，$e(S, S)$ 简写为 $e(S)$。对于顶点 $v \in V(G)$，设 $N_S(v)$ 为 $v$ 在 $S$ 中的邻居集，即 $N_S(v) = N_G(v) \cap S$，$d_S(v)$ 为其基数。此外，我们用 $G[S]$ 表示 $G$ 由 $S$ 导出的子图。若 $G[S]$ 是 $G$ 的一个完全子图，则称 $G[S]$ 为团。

设 $G_1$ 和 $G_2$ 为两个图。$G_1$ 和 $G_2$ 的不交并记为 $G_1 \cup G_2$。$G_1$ 和 $G_2$ 的联记为 $G_1 \vee G_2$，其构造方式是从 $G_1 \cup G_2$ 出发，插入 $G_1$ 的每个顶点与 $G_2$ 的每个顶点之间的所有可能边。设 $S_{n, k_1^l} = K_1 \vee ((K_{k-1} \vee (n-k-l)K_1) \cup lK_1)$ 和 $S_{n, k_1^l} = K_l \vee ((K_{k-l} \vee (n-k-1)K_1) \cup K_1)$，其中 $1 \leq l \leq k-1$。特别地，当 $l = 1$ 时，$S_{n, k_1^1}$ 理解为图 $K_1 \vee ((K_{k-1} \vee (n-k-1)K_1) \cup K_1)$。

设 $S_l$ 表示 $l+1$ 个顶点的星形图。$S_l$ 中度数为 $l$ 的顶点称为中心顶点。星形森林是各连通分支均为星形的森林。

给定 $n$ 个顶点的图 $G$，其邻接矩阵 $A(G) = (a_{ij})_{n \times n}$ 定义为一个 $(0,1)$-矩阵，其中 $a_{ij} = 1$ 当且仅当 $v_i \sim v_j$。由于 $A(G)$ 是实对称矩阵，其特征值全为实数，排列为 $\lambda_1(G) \geq \cdots \geq \lambda_n(G)$。谱半径 $\lambda(G)$ 定义为 $A(G)$ 所有特征值中的最大模。根据 Perron–Frobenius 定理，若 $G$ 是连通的，则 $\lambda(G) = \lambda_1(G)$，且存在唯一的正特征向量 $x = (x_1, \ldots, x_n)^T$ 对应于 $\lambda(G)$，其中 $x_i$ 可视为顶点 $v_i$ 的权重。我们称 $x$ 为 $G$ 的 Perron 向量。

**预备知识**

本节给出一些预备结果，将在后续节中用于证明我们的主要结果。

**引理 2.1** [21]、[24]

设 $u, v$ 为连通图 $G$ 中的两个不同顶点。假设 $v_1, v_2, \ldots, v_s$（$1 \leq s \leq d_G(v)$）是 $N_G(v) \setminus N_G(u)$ 中的一些顶点，$x$ 是 $A(G)$ 的 Perron 向量，坐标 $x_z$ 对应于 $z \in V(G)$。设 $G' = G - \{vv_i : 1 \leq i \leq s\} + \{uv_i : 1 \leq i \leq s\}$。若 $x_u \geq x_v$，则 $\lambda(G) < \lambda(G')$。

**引理 2.2** [7]

设 $G$ 为连通图。若 $H$ 是 $G$ 的一个真子图，则 $\lambda(H) < \lambda(G)$。

**引理 2.3** [7]

若 $G$ 为连通图，则 $\lambda(G) \leq \Delta(G)$。

**定理 1.3 的证明**

本节给出定理 1.3 的证明。设 $F = \bigcup_{i=1}^{k+1} S_{\ell_i}$ 为一个星形森林，其中 $k \geq 2$ 且 $i \in [k+1]$ 时 $\ell_i \geq 1$。设 $G^*$ 是 $G(m, F)$ 中达到最大谱半径的图。

注意 $m \geq (7k+7)^2 (\sum_{i=1}^{k+1} \ell_i + k - 1)^2$ 且 $m + \frac{k(k+1)}{2} \equiv l \pmod{k}$（其中 $1 \leq l \leq k-1$）。显然，$S_{\frac{m-lk}{k+k}+3/2, k_1, l}$ 是 $G(m, F)$ 中的一个图。由引理 2.4，我们有

$$\lambda(G^*) \geq \lambda(S_{\frac{m-lk}{k+k}+3/2, k_1, l}) > k - 1 + \sqrt{4m - k^2} - \frac{k+1}{2},$$

这给出了

$$\lambda^2(G^*) - (k-1)\lambda(G^*) > m + \gamma - \frac{k}{4},$$

其中 $\gamma = -\frac{k(k-1)}{2}$。

此外，由定理 1.2，容易看出 $\frac{5}{4}m > k - 1 + \sqrt{4m - k^2} + \frac{1}{2} > \lambda(G^*) > \ldots$

**结论性评论**

令人感兴趣的是，Brualdi–Hoffman–Turán 型问题吸引了越来越多的研究者关注。在本文中，我们为这一问题做出了基础性贡献。基于广泛的研究，一个明显的现象是：对于足够大的 $m$，某些 $F$-自由图（边数为 $m$）达到相同的谱半径上界 $\rho(G) \leq k - 1 + \sqrt{4m - k^2} + \frac{1}{2}$，等号成立当且仅当 $G \cong K_k \vee (\frac{m-k}{k} - \frac{1}{2}) K_1$。上述现象在以下情形中成立：

? $G \in G(m, C_{2k+1}) \cup G(m, \ldots)$

**利益冲突声明**

作者声明不存在已知的竞争性财务利益或个人关系可能影响本文所报告的工作。

**致谢**

作者感谢审稿人的宝贵意见和建设性建议，这些意见和建议帮助我们显著改进了本文稿。Shuchao Li 得到国家自然科学基金（批准号 12571365, 12171190）的资助。

Honghao Chen | Shuchao Li