[中文标题] 谱半径与给定分数性质的图中完美匹配的紧密关系研究

《Discrete Applied Mathematics》：Spectral radius and perfect matching in graphs with given fractional property

[编辑推荐] 这篇论文聚焦图论与谱理论交叉领域，探讨图的谱半径如何作为判定其结构特性的有力工具。作者建立了几个“紧的”充分条件，解决了从分数完美匹配的存在性（必要条件）推断出（常规）完美匹配存在性（充分条件）的关键问题，并提出并回答了类似性质的推广问题，如分数k-因子临界性（fractional k-factor-criticality）与k-因子临界性（k-factor-criticality）之间的关系。研究展示了利用谱半径（spectral radius）这一代数工具来分析图的结构性质（如完美匹配、因子临界性）的有效性和精确性，丰富了图论中谱极值问题的研究成果。

　　

[摘要翻译]

亮点

图G的一个完美匹配是指一个匹配，使得图G的每个顶点都恰好与该匹配中的一条边相关联。图G的一个分数完美匹配是一个函数h，赋予每条边一个在[0, 1]之间的数，使得对于每个顶点 v ∈ V(G)，都有 ∑_{e ∈ E_G(v)} h(e) = 1，其中 E_G(v) 是与顶点 v 相关联的边集。显然，一个图中分数完美匹配的存在性是它包含完美匹配的必要条件。在本文中，我们提出了一个紧的谱半径条件，该条件保证了一个拥有分数完美匹配的图包含一个完美匹配。

一个图G被称为k-因子临界的，如果删除任意k个顶点后，剩余子图仍然拥有一个完美匹配。一个图G被称为分数k-因子临界的，如果删除任意k个顶点后，剩余子图仍然拥有一个分数完美匹配。显然，一个图的分数k-因子临界性是它是k-因子临界图的必要条件。在本文中，我们提出了一个基于谱半径的紧的充分条件，该条件保证了一个具有分数k-因子临界性的图是k-因子临界的。

引言

让G是一个无向、简单且连通的图，顶点集为V(G)，边集为E(G)。G的阶和大小分别用|V(G)| = n和|E(G)| = e(G)表示。我们用c(G)和o(G)分别表示G的连通分支数和奇数分支数。对于一个顶点子集 S ? V(G)，用G[S]表示由S诱导的子图，|S|表示S的大小。令G₁和G₂是两个不相交的图。我们用G₁∪ G₂表示G₁和G₂的不交并。连接G₁∨ G₂是通过在G₁∪ G₂的基础上，添加V(G₁)和V(G₂)之间所有可能的边而得到的图。图G的韧性定义为 τ(G) = min{ |S| / c(G-S) : S是G中的一个顶点割集}，其中 G ≠ K_n。

给定一个n阶图G，其邻接矩阵A(G) = (a_ij)_{n×n}是一个0-1矩阵，其中如果顶点 v_i～ v_j，则 a_ij=1，否则为0。注意A(G)是一个实非负对称矩阵，因此其特征值是实数，可以按非递增顺序排列为 λ₁(G) ≥ λ₂(G) ≥ … ≥ λ_n(G)。A(G)的最大特征值，记作 ρ(G)，被称为图G的谱半径。

如果性质A蕴含性质B，那么性质B是性质A的一个必要条件。这引出了一个有趣的问题。

问题 1.1

对于一个具有性质B的图，保证其具有性质A的充分条件是什么？

许多研究者对问题1.1给予了大量关注。注意，2-连通性是一个图包含哈密顿环的必要条件。对应于问题1.1，一个自然而有趣的问题出现了：保证一个2-连通图包含哈密顿环的充分条件是什么？1974年，Goodman和Hedetniemi [8] 提出了一个基于禁止子图的充分条件，确保一个2-连通图包含哈密顿环。

定理 1.1 Goodman和Hedetniemi [8]

每个2-连通的 {K_1,3, K_1,3+e} - 自由图包含一个哈密顿环。

Matthews和Sumner [11] 证明了每个2-连通的n阶无爪图，如果最小度 δ(G) ≥ (n-2)/3，则包含一个哈密顿环。Fan [2] 证明了如果对每一对距离为2的顶点 u, v，都有 max{d_G(u), d_G(v)} ≥ n/2，那么该2-连通图就有一个哈密顿环。Faudree和Gould [5] 证明了对于n≥10，一个2-连通的H-自由图包含哈密顿环当且仅当H是以下图族之一：{K_1,3, P₄}, {K_1,3, P₅}, {K_1,3, P₆}, {K_1,3, C₃}, {K_1,3, Z₁}, {K_1,3, Z₂}, {K_1,3, Z₃}, {K_1,3, B}, {K_1,3, W}, {K_1,3, N}（见图1），其中Z_i是将一个C₃的一个顶点与一个P_i+1的一个端点重合而形成的图，其中 i ∈ {1, 2, 3}。

注意，1-韧性是一个图包含哈密顿环的必要条件。对应于问题1.1，一个自然而有趣的问题出现了：保证一个1-韧图包含哈密顿环的谱充分条件是什么？令 K_n-4⁺³表示在 3K₁∪ K_n-4的基础上，添加3条K_n-4和3K₁之间独立边而得到的图。最近，Fan、Lin和Lu [4] 提出了一个紧的谱充分条件，保证了一个连通的1-韧图包含哈密顿环。

定理 1.2 Fan, Lin和Lu [4]

假设G是一个连通的1-韧图，阶数 n ≥ 18，且最小度 δ ≥ 2。如果 ρ(G) ≥ ρ(K₁∨ K_n-4⁺³)，那么G包含一个哈密顿环，除非 G ? K₁∨ K_n-4⁺³。

图G的一个完美匹配是一个匹配，使得图G的每个顶点都恰好与该匹配中的一条边相关联。图G的一个分数完美匹配是一个函数h，赋予每条边一个在[0, 1]之间的数，使得对于每个顶点 v ∈ V(G)，都有 ∑_{e ∈ E_G(v)} h(e) = 1，其中 E_G(v) 是与顶点 v 相关联的边集。显然，一个图中分数完美匹配的存在性是它包含完美匹配的必要条件。对应于问题1.1，我们提出了以下问题。

问题 1.2

保证一个拥有分数完美匹配的图包含完美匹配的紧的谱半径条件是什么？

针对问题1.2，我们建立了以下结果。

定理 1.3

令G是一个拥有分数完美匹配的连通图，偶数阶 n ≥ 12。如果 ρ(G) ≥ ρ(K₁∨ (K_n-5∪ K₃∪ K₁))，那么G包含一个完美匹配，除非 G ? K₁∨ (K_n-5∪ K₃∪ K₁)。

事实上，O [13] 提出了一个基于谱半径的充分条件，保证一个连通图包含一个完美匹配。

定理 1.4 O [13]

令 n ≥ 8 是一个偶数或 n=4。如果G是一个n顶点图，且 ρ(G) > θ(n)，其中θ(n)是方程 x3 - (n-4)x2 - (n-1)x + 2(n-4) = 0 的最大根，那么G有一个完美匹配。对于 n=6，如果 ρ(G) > (1+√33)/2，那么G有一个完美匹配。

可以验证 ρ(K₁∨ (K_n-3∪ 2K₁)) = θ(n)。根据引理2.1，我们可以证明对于 n ≥ 12，有 ρ(K₁∨ (K_n-5∪ K₃∪ K₁)) < ρ(K₁∨ (K_n-3∪ 2K₁))。

一个图G被称为k-因子临界的，如果删除任意k个顶点后，剩余子图仍然拥有一个完美匹配。一个图G被称为分数k-因子临界的，如果删除任意k个顶点后，剩余子图仍然拥有一个分数完美匹配。显然，如果G是k-因子临界的，那么它必然是分数k-因子临界的，然而反之不一定普遍成立。对应于问题1.1，我们提出了以下问题。

问题 1.3

保证一个具有分数k-因子临界性的图是k-因子临界的紧的谱半径条件是什么？

关于问题1.3，我们证明了以下结果。

定理 1.5

令G是一个具有分数k-因子临界性的连通图，阶数 n ≥ max{k+56, 23k+20}，其中 n ≡ k (mod 2) 且 k ≥ 1 是一个整数。如果 ρ(G) ≥ ρ(K_k∨ (K_n-k-3∪ K₃))，那么G是k-因子临界的，除非 G ? K_k∨ (K_n-k-3∪ K₃)。

事实上，Zhang和Fan [16] 提出了一个基于谱半径的充分条件，保证一个连通图是k-因子临界的。

定理 1.6 Zhang和Fan [16]

令k和n是两个正整数，满足 n ≡ k (mod 2)，且令G是一个n阶连通图。如果 ρ(G) ≥ ρ(K_k∨ (K_n-k-1∪ K₁))，那么G是k-因子临界的，除非 G ? K_k∨ (K_n-k-1∪ K₁)。

可以验证对于 n ≥ k+5，有 ρ(K_k∨ (K_n-k-3∪ K₃)) < ρ(K_k∨ (K_n-k-1∪ K₁))。

一个图G被称为k-可扩张的，如果它有一个k-匹配，并且G的每一个k-匹配M都包含在G的一个完美匹配中。一个图G被称为分数k-可扩张的，如果对于任何k-匹配M，都存在一个包含M的分数完美匹配。显然，如果G是k-可扩张的，那么它必然是分数k-可扩张的，然而反之不一定成立。我们提出了以下问题。

问题 1.4

保证一个具有分数k-可扩张性的图是k-可扩张的紧的谱半径条件是什么？

显然，一个2k-因子临界图必须是k-可扩张的。根据定理1.5，我们可以很容易推导出以下结果。

推论 1.1

令G是一个具有分数k-可扩张性的连通图，阶数 n ≥ 46k+20，其中n是偶数且 k ≥ 1 是一个整数。如果 ρ(G) ≥ ρ(K_2k∨ (K_n-2k-3∪ K₃))，那么G是k-可扩张的，除非 G ? K_2k∨ (K_n-2k-3∪ K₃)。

Miao, Li和Wei [12] 提出了一个基于谱半径的充分条件，保证一个连通图是k-可扩张的。

定理 1.7 Miao, Li和Wei [12]

令k是一个正整数，n是一个偶正整数。如果G是一个n顶点的连通图，且 ρ(G) ≥ ρ(K_2k∨ (K_n-2k-1∪ K₁))，那么G是k-可扩张的，除非 G ? K_2k∨ (K_n-2k-1∪ K₁)。