奇偶[a,b]-因子谱极值问题的完全解

《Discrete Applied Mathematics》：Complete solutions to spectral extremal problems on parity [ a,b]-factors

　　

## 摘要

图 $G$ 的绑定数 $b(G)$ 定义为对图 $G$ 中所有满足 $N_G(X) \neq V(G)$ 的非空顶点集 $X \subseteq V(G)$ 取 $|N_G(X)|/|X|$ 的最小值。若 $b(G) \geq 1$，则称图 $G$ 为 1-绑定图。Fan 和 Lin [Electron. J. Combin. 31 (2024) P1.30] 提出了一个有趣的问题：哪些满足 $\delta(G) \geq k$ 的 1-绑定图具有 $k$-因子？Fan 和 Lin 已解决该问题中 $k=1, 2$ 的情形，Tang 和 Zhang 则完成了所有 $k \geq 2$ 的情况。这自然引出了一个新的引人入胜的问题：对于满足 $\delta(G) \geq a$ 的 1-绑定连通图，保证其具有奇偶 $[a,b]$-因子的紧致谱半径条件是什么？Fan 等人已解决 $1=a \leq b$ 的情形，Tang 和 Zhang 已解决 $2 \leq a = b$ 的情形。对于一般的 $2 \leq a < b$，本文给出了该问题的完整解答。

图的韧性 $t(G) = \min\{|X|/c(G-X) : X \text{ 是 } G \text{ 的顶点割集}\}$，其中 $G \not\cong K_n$。若 $t(G) \geq t$，则称图 $G$ 为 $t$-韧性图。Liu 等人 [Discrete Math. 348 (2025) 114593] 提出了一个有趣的问题：保证韧性图中因子存在的紧致谱半径条件是什么？Fan 等人已解决 $a = b = 2$ 时的奇偶 $[a,b]$-因子问题。Chen 等人已解决 $3 \leq a = b$ 的情形。本文给出了 Liu-Fan-Shu 问题中 $2 \leq a < b$ 时奇偶 $[a,b]$-因子的完整解答。

## 引言

本文所考虑的所有图均为有限、简单且无向的。设 $G$ 为顶点集为 $V(G)$、边集为 $E(G)$ 的图。$G$ 的阶和大小分别记为 $|V(G)| = n$ 和 $|E(G)| = e(G)$。设 $c(G)$ 为 $G$ 的连通分支数。设 $\bar{G}$ 为 $G$ 的补图。对任意两个顶点不相交的图 $G_1$ 和 $G_2$，$G_1 \cup G_2$ 表示 $G_1$ 和 $G_2$ 的不相交并。对任意顶点 $v \in V(G)$，$d_G(v)$ 和 $N_G(v)$ 分别表示 $v$ 在 $G$ 中的度和邻域。令 $\delta(G) = \min_{v \in V(G)} d_G(v)$。我们用 $u \sim v$ 表示 $u$ 与 $v$ 相邻。对 $V(G)$ 的任意子集 $S$，$G[S]$ 表示 $G$ 由 $S$ 诱导的子图。进一步，对 $V(G)$ 的任意子集 $S$，$G - S$ 表示诱导子图 $G[V(G) - S]$。对两个顶点不相交的子集 $S, T \subseteq V(G)$，$|[S,T]|_G$ 表示 $S$ 与 $T$ 之间的边数。

设 $A(G)$ 为 $G$ 的邻接矩阵，$\rho(G) = \lambda_1(G) \geq \lambda_2(G) \geq \cdots \geq \lambda_n(G)$ 为其特征值。由 Perron-Frobenius 定理，每个连通图 $G$ 对应 $\rho(G)$ 存在正的单位特征向量，称为 $A(G)$ 的 Perron 向量。

$G$ 的 $[a,b]$-因子是一个生成子图 $H$，使得对每个顶点 $v \in V(G)$ 有 $a \leq d_H(v) \leq b$，其中 $a$ 和 $b$ 是两个满足 $a \leq b$ 的正整数。若 $a = b = k$，则 $[a,b]$-因子称为 $k$-因子。$G$ 的奇偶 $[a,b]$-因子是一个生成子图 $H$，使得对每个顶点 $v \in V(G)$ 有 $a \leq d_H(v) \leq b$ 且 $d_H(v) \equiv a \equiv b \pmod{2}$。

Liu 等人 [12] 证明了以下定理。

**定理 1.1**（Liu 等人 [12]）设 $a$、$b$ 和 $n$ 是三个正整数，满足 $a \leq b$、$a \equiv b \pmod{2}$ 且 $na$ 为偶数。设 $G$ 是阶为 $n$ 的图。则 $G$ 不具有奇偶 $[a,b]$-因子当且仅当存在 $V(G)$ 的两个不相交子集 $S$ 和 $T$，使得
$$\sum_{x \in T} d_{G-S}(x) \leq a|T| - b|S| + q_G(S,T) - 2,$$
其中 $q_G(S,T)$ 表示 $G - S - T$ 中满足 $a|V(Q)| + |[V(Q),T]|_G \equiv 1 \pmod{2}$ 的连通分支 $Q$ 的个数。

对任意 $X \subset V(G)$，令 $N_G(X) = \bigcup_{x \in X} N(x)$。绑定数由 Woodall [14] 首次引入。图 $G$ 的绑定数 $b(G)$ 定义为
$$b(G) = \min\left\{\frac{|N_G(X)|}{|X|} : \emptyset \neq X \subseteq V(G),\, N_G(X) \neq V(G)\right\}.$$
若 $b(G) \geq 1$，则称图 $G$ 为 1-绑定图。作为衡量图连通性和脆弱性的经典参数，绑定数与因子的存在性密切相关。Anderson [1] 证明了一个阶为偶数且 $b(G) \geq 4/3$ 的图 $G$ 具有完美匹配。Woodall [14] 指出 $b(G) \geq 3/2$ 的图 $G$ 保证存在 Hamilton 回路，从而具有连通的 2-因子。注意 $\delta(G) \geq k$ 是图 $G$ 包含 $k$-因子的平凡必要条件。Katerinis 和 Woodall [10] 证明：对 $n \geq 4k-6$ 满足 $b(G) \geq 2$ 的图 $G$（其中 $k \geq 2$），$G$ 包含 $k$-因子。

Fan 和 Lin [6] 提出了以下基本且具有挑战性的问题。

**问题 1.1** 哪些满足 $\delta(G) \geq k$ 的 1-绑定图具有 $k$-因子？

Fan 和 Lin [6] 解决了 $k = 1, 2$ 的情形。随后，Tang 和 Zhang [13] 完全解决了 $k \geq 2$ 时的问题 1.1。自然地，我们提出以下问题。

**问题 1.2** 保证满足 $\delta(G) \geq a$ 的 1-绑定连通图具有奇偶 $[a,b]$-因子的紧致谱半径条件是什么？

Fan 等人 [9] 解决了 $1 = a \leq b$ 时的问题 1.2。Tang 和 Zhang [13] 解决了 $2 \leq a = b$ 时的问题 1.2。对于一般的 $2 \leq a < b$，本文给出了问题 1.2 的完整解答。

下面我们给出图 $G_{n,ab}(G)$ 的定义。图 $G_{n,ab}(G)$ 的顶点集为
$$V(G_{n,ab}(G)) = \{u_1, \ldots, u_{a+1}\} \cup \{v_1, \ldots, v_{n-a-2}\} \cup \{w_1\},$$
边集为
$$E(G_{n,ab}(G)) = \{v_iv_j \mid 1 \leq i < j \leq n-a-2\} \cup \{u_iv_j \mid 1 \leq i \leq a, 1 \leq j \leq a-1\} \cup \{u_{a+1}v_i \mid i \in \{1,2,\ldots,a-2,a\}\} \cup \{u_iw_1 \mid 1 \leq i \leq a+1\}$$
（见图 1）。

**定理 1.2** 设 $a$、$b$ 和 $n$ 是三个正整数，满足 $2 \leq a < b$、$a \equiv b \pmod{2}$ 且 $na$ 为偶数。设 $G$ 是顶点数为 $n$ 的 1-绑定连通图，且 $n \geq \max\left\{\frac{136}{a}+264, \frac{2a}{b}+\frac{7}{b}+\frac{5a}{b}+14\right\}$，$\delta(G) \geq a$。若 $\rho(G) \geq \rho(G_{n,ab}(G))$，则 $G$ 包含奇偶 $[a,b]$-因子，除非 $G \cong G_{n,ab}(G)$。

1973 年，Chvátal [5] 定义了非完全图 $G$ 的韧性
$$t(G) = \min\left\{\frac{|X|}{c(G-X)} \;\middle|\; X \subset V(G),\, c(G-X) \geq 2\right\},$$
其中 $c(G-X)$ 表示 $G-X$ 的连通分支数。若 $t(G) \geq t$，则称 $G$ 为 $t$-韧性图。Katerinis 和 Woodall [10] 证明：若 $t(G) \geq (a-1) + a/b$ 且当 $a = b$ 时 $a|V(G)|$ 为偶数，则 $G$ 具有 $[a,b]$-因子，其中 $a$ 和 $b$ 是两个满足 $b \geq a$ 的整数。最近，Bian [2] 在某种意义上将上述结果推广到了奇偶 $[a,b]$-因子。

**定理 1.3**（Bian [2]）设 $G$ 是连通图，$a$ 和 $b$ 是两个满足 $b \geq a \geq 2$ 且 $a \equiv b \pmod{2}$ 的整数。若 $a|V(G)|$ 为偶数且 $t(G) \geq (a-1) + a/b$，则 $G$ 具有奇偶 $[a,b]$-因子。

Liu 等人 [11] 提出了一个有趣的问题。

**问题 1.3** 保证韧性图中因子存在的紧致谱半径条件是什么？

Fan 等人 [7] 解决了 $a = b = 2$ 时奇偶 $[a,b]$-因子的情况。Chen 等人 [4] 解决了 $3 \leq a = b$ 时的问题 1.3。本文给出了 $2 \leq a < b$ 时问题 1.3 中奇偶 $[a,b]$-因子的完整解答。

接下来我们定义图 $G_{n,a}^t(G)$，其顶点集为
$$V(G_{n,a}^t(G)) = \{u_1, \ldots, u_{a+1}\} \cup \{v_1, \ldots, v_{n-a-2}\} \cup \{w_1\},$$
边集为
$$E(G_{n,a}^t(G)) = \{v_iv_j \mid 1 \leq i < j \leq n-a-2\} \cup \{u_iv_j \mid 1 \leq i \leq a-1, 1 \leq j \leq a-1\} \cup \{u_av_i \in \{1,2,\ldots,a-2,a\}\} \cup \{u_{a+1}v_i \mid i \in \{1,2,\ldots,a-2,a+1\}\} \cup \{u_iw_1 \mid 1 \leq i \leq a+1\}$$
（见图 2）。

**定理 1.4** 设 $a$、$b$ 和 $n$ 是三个正整数，满足 $2 \leq a < b$、$a \equiv b \pmod{2}$ 且 $na$ 为偶数。设 $G$ 是顶点数为 $n$ 的 1-韧性连通图，且 $n \geq \max\left\{\frac{136}{a}+264, \frac{2a}{b}+\frac{7}{b}+\frac{5a}{b}+14\right\}$，$\delta(G) \geq a$。若 $\rho(G) \geq \rho(G_{n,a}^t(G))$，则 $G$ 包含奇偶 $[a,b]$-因子，除非 $G \cong G_{n,a}^t(G)$。

## 预备知识

本节介绍一些记号和辅助结果，这些是证明主要结果的关键。

**引理 2.1**（Brouwer 和 Haemers [3]）若 $H$ 是连通图 $G$ 的子图，则 $\rho(H) \leq \rho(G)$，等号成立当且仅当 $H \cong G$。

**引理 2.2**（Chvátal [5]）若 $H$ 是 $G$ 的生成子图，则 $t(H) \leq t(G)$。

**引理 2.3**（Wu 等人 [15]）设 $G$ 是连通图，$v_i, v_j \in V(G)$，$\emptyset \neq S \subseteq N(v_j) \setminus N(v_i)$。设 $G' = G - \{v_jv \mid v \in S\} + \{v_iv \mid v \in S\}$，$(x_1, \ldots, x_n)^T$ 是 $A(G)$ 的 Perron 向量，其中 $x_i$ 对应 $v_i$。若 $x_i \geq x_j$，则 $\rho(G') > \rho(G)$。

**引理 2.4**（Liu 等人 [12]）设 $G$ 是顶点数为 $n$ 的连通图，且……

## 定理 1.2 的证明

设 $a$、$b$ 和 $n$ 是三个正整数，满足 $2 \leq a < b$、$a \equiv b \pmod{2}$、$na$ 为偶数，且 $n \geq \max\left\{\frac{136}{a}+264, \frac{2a}{b}+\frac{7}{b}+\frac{5a}{b}+14\right\}$。设 $\mathcal{B}_{n,a,b}$ 为顶点数为 $n$ 的 1-绑定连通图 $G$ 的集合，其中 $\delta(G) \geq a$ 且 $G$ 不具有奇偶 $[a,b]$-因子。设 $G^*$ 是 $\mathcal{B}_{n,a,b}$ 中谱半径最大的图。令 $x = (x_u)_{u \in V(G^*)}$ 为 $A(G^*)$ 的 Perron 向量。下文我们将 $\rho(G^*)$ 简记为 $\rho$。注意 $G^*$ 不具有奇偶 $[a,b]$-因子。由定理 1.1，存在两个……

## 定理 1.4 的证明

设 $a$、$b$ 和 $n$ 是三个正整数，满足 $2 \leq a < b$、$a \equiv b \pmod{2}$、$na$ 为偶数，且 $n \geq \max\left\{\frac{136}{a}+264, \frac{2a}{b}+\frac{7}{b}+\frac{5a}{b}+14\right\}$。设 $\mathcal{T}_{n,a,b}$ 为顶点数为 $n$ 的 1-韧性连通图 $G$ 的集合，其中 $\delta(G) \geq a$ 且 $G$ 不具有奇偶 $[a,b]$-因子。设 $G^{**}$ 是 $\mathcal{T}_{n,a,b}$ 中谱半径最大的图。令 $x = (x_u)_{u \in V(G^{**})}$ 为 $A(G^{**})$ 的 Perron 向量。下文我们将 $\rho(G^{**})$ 简记为 $\rho^*$。注意 $G^{**}$ 不具有奇偶 $[a,b]$-因子。则存在两个不相交顶点……

## 结论性评论

回顾一下，$G$ 的 $[a,b]$-因子是一个生成子图 $H$，使得对每个顶点 $v \in V(G)$ 有 $a \leq d_H(v) \leq b$，其中 $a$ 和 $b$ 是两个满足 $a \leq b$ 的正整数。设 $H_{n,a,b}$ 是由 $K_a \vee (K_{n-a-b-1} \cup (b+1)K_1)$ 通过在 $(b+1)K_1$ 中的一个顶点和 $K_{n-a-b-1}$ 中的 $a-1$ 个顶点之间添加 $a-1$ 条边得到的图。最近，Fan 等人 [8] 证明了以下定理。

**定理 5.1**（Fan 等人 [8]）设 $a$ 和 $b$ 是两个满足 $b > a$ 的正整数，设 $G$ 是阶为 $n \geq 2(a+b+2)(b+2)$ 的连通图，且最小度 $\delta(G) \geq a$。若 $\rho(G) \geq \rho(H_{n,a,b})$，则……

## 利益冲突声明

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

## 致谢

作者感谢匿名审稿人对改进论文呈现方式提出的有益意见。

华才佳 | 徐婷 | 刘瑞芳