图的谱半径和$P_{\ge 2}$-因子的存在性

The Spectral Radius of Graphs and the Existence of $P_{\ge 2}$-Factors

摘要: 设$G$ 是简单连通图，若图$G$ 有一个生成子图$F$ ，该生成子图$F$ 的每个连通分支是阶数至少为2的路，则称图$G$ 含有一个$P_{\ge 2}$ -因子。本文给出了图$G$ 谱半径的一个下界，保证了该类图$P_{\ge 2}$ -因子的存在性，以及刻画了谱半径达到下界时对应的极图结构。设$f$ 为一个函数，对图$G$ 中的每条边赋一个落在区间$\left[0,1\right]$ 上的函数值。若满足${\displaystyle \sum _{e\in \Gamma \left(v\right)}f\left(e\right)}\le 1$ ，其中$\Gamma \left(v\right)$ 是与点$v$ 相邻的边的集合，则称$f$ 是图$G$ 的一个分数匹配。本文还根据分数完美匹配定理给出了图$G$ 含有一个$P_{\ge 2}$ -因子的充分性条件。

Abstract: Let $G$ be a simple connected graph. A $P_{\ge 2}$ -factor of a graph $G$ is a spanning subgraph $F$ of $G$ such that each component of $F$ is a path of order at least $k$ ($k\ge 2$ ). This paper provides a lower bound for the spectral radius of graph G, guarantees the existence of a $P_{\ge 2}$ -factor in such graphs, and characterizes the extremal graph structures when the spectral radius reaches the lower bound. A fractional matching is a function $f$ that assigns to each edge of a graph a number in [0, 1] so that, for each vertex $v$ , we have ${\displaystyle \sum f\left(e\right)}\le 1$ where the sum is taken over all edges incident to $v$ . This paper also provides a sufficient condition for a graph $G$ to contain a $P_{\ge 2}$ -factor based on the perfect matching theorem.

1. 引言

代数图论主要利用相关矩阵的代数性质来研究图的性质，矩阵的代数性质主要指矩阵的特征值和特征向量。一个图对应的矩阵特征值的集合称为图的谱，对图的谱性质与图结构之间关系的研究不仅能够促使图谱理论自身的发展，而且一直为许多其他领域的发展提供着有力的工具。图谱的研究主要是利用线性代数，矩阵论等成熟的理论和技巧，巧妙地把图的一些基本结构性质和它的关键参数联系在一起，并找出它们之间的内在关系。一个图对应的矩阵特征值的集合称为图的谱，对图的谱性质与图结构之间关系的研究不仅能够促使图谱理论自身的发展，而且一直为许多其他领域的发展提供着有力的工具。图谱的研究主要是利用线性代数，矩阵论等成熟的理论和技巧，巧妙地把图的一些基本结构性质和它的关键参数联系在一起，并找出它们之间的内在关系。可以更加深刻地对图的离散程度的内在关系进行刻画，因此谱半径是图谱理论不可或缺的工具。

设$G=\left(V\left(G\right),E\left(G\right)\right)$ 是一个具有$n$ 个顶点和$m$ 条边的简单连通图，图$G$ 的补图记为$\overline{G}$ 。$K_n$ 是阶数为$n$ 的完全图，特别地，$t{K}_1$ 表示完全图$K_t$ 的补图。$n$ 阶图$G$ 的邻接矩阵$A\left(G\right)={\left(a_{ij}\right)}_{n\times n}$ 为一个$n\times n$ 阶实对称矩阵且满足

$a_{ij}=\{\begin{array}{l}1,v_i和v_j相�;\\ 0,v_i和v_j不相�.\end{array}$

图$G$ 的邻接矩阵所对应的特征多项式的最大根定义为${\lambda }_1\left(G\right)$ ，是图$G$ 的谱半径。若图$G$ 有一个生成子图，该生成子图的每个分支是阶数至少为2的路，则称该图有一个$P_{\ge 2}$ -因子。

邻接谱半径反映了图的整体连通性和稠密性，与图的结构紧密相关。由于理论和实际的需要，估计图谱的界是许多人关心的事，尤其是对图的最大特征值的估界。将图依照它们的谱进行分类和排序，这是著名图谱专家Dragos等人于1985年在文献[1]中提出的图谱进一步研究的十二个方向之一，至今仍为图谱研究的热点。对于一个给定的图类确定该图类中图的谱半径的上界并刻画达到该上界的图，这是Richard等人于1985年在文献[2]中提出的关于图的谱半径的一个问题。此后，这个问题被广泛地研究。

邻接谱吸引了许多学者对其进行研究。在2004年，Liu等人在文献[3]中刻画了给定割边数的图类中谱半径达到最大时的极图结构，Feng等在2006年的文献[4]中给出了给定匹配数的连通图的邻接谱半径上界，并刻画相对应的极图结构，Suil在2016年的文献[5]中结合分数匹配数给出了最小度为$d$ 的图类中谱半径的一个严格上界。文献[6]中，Hu和Zhang在2024年给出了简单连通图距离谱半径的一个上界保证了该种图类中含有一个[1, b]-因子。

$P_{\ge 2}$ -因子的研究在图论和组合数学中具有重要意义，研究$P_{\ge 2}$ -因子的存在条件(如谱半径、边连通性等)有助于揭示图的全局结构性质。Akiyama等人文献[7]中给出图中含有一个$P_{\ge 2}$ -因子的充要条件，为后续$P_{\ge 2}$ -因子的研究提供了一个重要的工具。文献[8]中，Zhang和Zhou于2009年定义了$P_{\ge 2}$ -因子覆盖图，并给出了一个图是$P_{\ge 2}$ -因子覆盖图的充要条件。Zhou和Sun在文献[9]中结合联结数给出了图是一个$P_{\ge 2}$ -因子一致图的充分条件。

本文只研究连通的简单图。匹配问题属于图论中的一个NP难问题，近几年在特殊的图类中结合一些参数给出了具有完美匹配的一些刻画。受上述谱半径结合某些参数研究的启发，本文从Akiyama等人在文献[7]中给出图中含有一个$P_{\ge 2}$ -因子的充要条件出发，结合图的谱半径的相关性质给出了简单图谱半径的一个下界，保证了图中$P_{\ge 2}$ -因子的存在性，并刻画了谱半径达到下界时的极图结构。特别地，本文还结合Scheinerman和Ullman于文献[10]中给出的一个完美分数匹配的充要性条件得出了图含有一个$P_{\ge 2}$ -因子的充分性条件。

2. 准备工作

对于连通图$G$ ，将$G$ 的孤立顶点个数记作$i\left(G\right)$ 。对于任意一个点子集$S\subseteq V\left(G\right)$ ，$G-S$ 表示由通过删除图$G$ 中的点子集$S$ 中的顶点和与点子集$S$ 相邻的边而得到的图，$\left|S\right|$ 是点集$S$ 中点的个数，$G\left[S\right]$ 是由点集$S$ 诱导的子图。$G\cup H$ 为图$G$ 和图$H$ 的不交并，不交图$G$ 和图$H$ 的联图$G\vee H$ 是指在$G\cup H$ 中，把图$G$ 的每个顶点和图$H$ 的每个顶点连接起来所得到的图。特别地，$K_m\vee \left(K_{n-m-t}\cup t{K}_1\right)$ 表示$K_m$ 中的所有点与$K_{n-m-t}$ 中的所有点和$t{K}_1$ 中的所有点相邻。

接下来的一个引理给出了图中含有一个$P_{\ge 2}$ -因子的充要条件。

引理2.1 [7] 若图$G$ 有一个$P_{\ge 2}$ -因子当且仅当对于任意一个点子集$S\subseteq V\left(G\right)$ ，有

$i\left(G-S\right)\le 2\left|S\right|.$

由Perron-Frobenius可得到下列引理，该引理揭示了一个图和它子图的谱半径关系。

引理2.2 [11] 设图$G$ 是一个连通图，$H$ 是图$G$ 的一个子图，则由${\lambda }_1\left(H\right)\le {\lambda }_1\left(G\right)$ ，当且仅当$G=H$ 时等号成立。

定义2.3 [11] 设$A$ 是一个实对称矩阵，其行指标和列指标均为$X=\left\{1,2,\cdots ,n\right\}$ ，给定$X$ 的一个划分$\Pi =\left\{X_1,X_2,\cdots ,X_m\right\}$ ，将行列指标根据$\Pi$ 进行分块，即

$A=\left(\begin{array}{ccc}{A}_{1,1}& \cdots & A_{1,m}\\ ⋮& \ddots & ⋮\\ A_{m,1}& \cdots & A_{m,m}\end{array}\right)$

其中$A_{i,j}$ 是由$X_i$ 中的行和$X_j$ 中的列划分而成的分块矩阵。定义$b_{ij}$ 为$A_{i,j}$ 的平均行和，则$B_{\Pi }=\left(b_{ij}\right)$ 称为矩阵$A$ 在划分$\Pi$ 下的商矩阵。如果每块$A_{i,j}$ 的行和是个常数，那么该划分是公平的，则称$B_{\Pi }$ 为矩阵$A$ 在公平划分$\Pi$ 下的公平商矩阵。

引理2.4 [11] 设$A$ 是一个实对称矩阵，$B_{\Pi }$ 是矩阵$A$ 在公平划分$\Pi$ 下的公平商矩阵，那么$B_{\Pi }$ 的特征值也是矩阵$A$ 的特征值。特别的，当矩阵$A$ 是一个非负不可约矩阵，则

${\lambda }_1\left(B_{\Pi }\right)={\lambda }_1\left(A\right).$

设$f$ 为一个函数，对图$G$ 中的每条边赋一个落在区间$\left[0,1\right]$ 上的函数值。若满足${\displaystyle {\sum }_{e\in \Gamma \left(v\right)}f\left(e\right)}\le 1$ ，其中$\Gamma \left(v\right)$ 点$v$ 相邻的边的集合，则称$f$ 是图$G$ 的一个分数匹配。在所有分数匹配$f$ 中，${\displaystyle {\sum }_{e\in \Gamma \left(v\right)}f\left(e\right)}$ 取得最大的数称为分数匹配数。若一个图的分数匹配数为$\frac{n}{2}$ ，则称该图具有完美分数匹配。

下面这个引理为Scheinerman和Ullman在文献[10]中给出的一个图中有完美分数匹配的充要性条件：

引理2.5 [10] 设$G$ 有完美分数匹配当且仅当$i\left(G-S\right)\le \left|S\right|$ 对所有的$S\subseteq V\left(G\right)$ 成立。

3. 基于谱半径下界的图G中$P_{\ge 2}$ -因子的存在性

本节主要利用引理1.1中$P_{\ge 2}$ -因子存在的充要性条件，确定在$n$ 阶连通图$G$ 中谱半径的下界以保证$P_{\ge 2}$ -因子的存在性，并刻画出谱半径达到下界时的极图结构。

图$G$ 中任意顶点$v$ 的邻点集记为$N_G\left(v\right)$ 。若两个图$G$ 和$H$ 同构，则记为$G\cong H$ 。

定理3.1 设图$G$ 是一个$n$ 阶连通图，若图$G$ 的谱半径满足

${\lambda }_1\left(G\right)>\{\begin{array}{l}\frac{1+\sqrt{41}}{2},n=7\\ \theta \left(n\right),n\ge 4且n\ne 7\end{array},$

则图$G$ 含有一个$P_{\ge 2}$ -因子，其中$\theta \left(n\right)$ 为$x^3-\left(n-5\right)x^2-\left(n-1\right)x+3n-15=0$ 的最大根。

证明 设$\Im$ 为一个不含$P_{\ge 2}$ -因子的所有$n$ 阶简单连通图的集合，且图$G$ 为$\Im$ 中谱半径达到最大的一个图，则由引理2.1可得，存在一个$S\subseteq V(G)$ 使得$i\left(G-S\right)\ge 2\left|S\right|+1$ 。下证定理3.1的逆否命题，即证图$G$ 的谱半径上界和达到上界时的极图结构。记$i\left(G-S\right)=i$ ，$\left|S\right|=s$ ，$I\left(G-S\right)$ 为删除图$G$ 中的点子集$S$ 中的顶点和与点子集$S$ 相邻的边后出现的孤立点集合。若$G-S$ 的所有连通分支和$G\left[S\right]$ 均不是团，那么由Perron-Frobenius定理可得，每增加一条边，图的谱半径会增大，与图$G$ 的谱半径是最大矛盾，所以由引理2.2得$G-S$ 的所有连通分支和$G\left[S\right]$ 均是团，且$G-S$ 至多只有一个非平凡连通分支。否则设有两个非平凡连通分支$Q_1$ 和$Q_2$ ，则任选$Q_1$ 中的一个点与$Q_2$ 中的一个点相连，由引理2.2得此时的谱半径增大，与图$G$ 的谱半径是最大矛盾。进一步可得所有连接$G-S$ 和$G\left[S\right]$ 的所有边均在图$G$ 中，否则由引理2.2可得存在一个谱半径比图$G$ 大的图，矛盾。接下来考虑下面两种情况：

情形1：$G-S$ 的所有连通分支中只有一个非平凡连通分支。

此时有$i=2s+1$ ，且$G\cong K_s\vee \left(K_{n-3s-1}\cup \left(2s+1\right)K_1\right)$ (如图1所示)。若不然设$i\ge 2s+2$ ，令$C_1$ 为$G-S$ 的一个非平凡连通分支，且$\left|V\left(C_1\right)\right|=n_1$ ，则$n_1\ge 2$ 。将$I\left(G-S\right)$ 中的一个点与$C_1$ 中的所有点相连得到的图定义为$G_1$ ，则由引理2.2得图$G_1$ 的谱半径比图$G$ 的谱半径大，与图$G$ 的谱半径最大矛盾，所以$i=2s+1$ 。此时点集$S$ 中的点应该与$C_1$ 中的所有点以及$I\left(G-S\right)$ 中的所有点相邻，否则由引理2.2可得与图$G$ 的谱半径最大矛盾，由此可推得此时$G\cong K_s\vee \left(K_{n-3s-1}\cup \left(2s+1\right)K_1\right)$ 。考虑$V\left(G\right)$ 的一个划分：$S\cup I\left(G-S\right)\cup V\left(C_1\right)$ ，则$A\left(G\right)$ 在该划分下对应的商矩阵为

$M_1=\left(\begin{array}{ccc}s-1& 2s+1& n-3s-1\\ s& 0& 0\\ s& 0& n-3s-2\end{array}\right)$

令$f_1\left(x\right)$ 为商矩阵$M_1$ 对应的特征方程，则

$f_1\left(x\right)=x^3-\left(n-2s-3\right)x^2-\left(n+2s^2-s-2\right)x+ns+2n{s}^2-7s^2-6s^3$ 。

设${\rho }_1$ 为$f_1\left(x\right)=0$ 的最大根，由于该点集划分是公平划分，由引理2.4得${\lambda }_1\left(G\right)={\rho }_1$ 。下证$G\cong K_1\vee \left(K_{n-4}\cup 3K_1\right)$ ：

令$f_1\left(x\right)$ 中的$s$ 为1，可得$f\left(x\right)=x^3-\left(n-5\right)x^2-\left(n-1\right)x+3n-13$ ，设$f\left(x\right)=0$ 的最大根为$\theta \left(n\right)$ ，则$f\left(x\right)$ 为图$K_1\vee \left(K_{n-4}\cup 3K_1\right)$ 在某个公平划分下对应的商矩阵的特征多项式。下证当$s\ge 2$ 时，图$K_s\vee \left(K_{n-3s-1}\cup \left(2s+1\right)K_1\right)$ 的谱半径比图$K_1\vee \left(K_{n-4}\cup 3K_1\right)$ 的谱半径小，所以此时$G\cong K_1\vee \left(K_{n-4}\cup 3K_1\right)$ 。由于${\lambda }_1\left(G\right)={\rho }_1>{\lambda }_1\left(K_{s+2}\right)=s+1$ ，且$n=n_1+3s=1\ge 3\text{s}+3$ 。且$f\left({\rho }_1\right)-f_1\left({\rho }_1\right)$ 可以看成一个以${\rho }_1$ 为自变量且开口向下的二次函数，则

$\begin{array}{c}f\left({\rho }_1\right)-f_1\left({\rho }_1\right)=\left(s-1\right)\left[-2{\rho }_1^2+\left(2s+1\right){\rho }_1-n\left(2s+3\right)+6s^2+13s+15\right]\\ <\left(s-1\right)\left[-2{\left(s+1\right)}^2+\left(2s+2\right)\left(s+1\right)-\left(3s+3\right)\left(2s+3\right)+6s^2+13s+15\right]\\ =-\left(s-1\right)\left(3s-5\right)\\ <0,\end{array}$

所以$f\left({\rho }_1\right)<f_1\left({\rho }_1\right)=0$ ，即${\lambda }_1\left(G\right)={\rho }_1<\theta \left(n\right)$ ，由此可得图$K_1\vee \left(K_{n-4}\cup 3K_1\right)$ 的谱半径比图$K_s\vee \left(K_{n-3s-1}\cup \left(2s+1\right)K_1\right)$ 的谱半径大，从而此时$G\cong K_1\vee \left(K_{n-4}\cup 3K_1\right)$ ，否则与图$G$ 的谱半径最大矛盾。

Figure 1. $K_s\vee \left(K_{n-3s-1}\cup \left(2s+1\right)K_1\right)$

图1. 图$K_s\vee \left(K_{n-3s-1}\cup \left(2s+1\right)K_1\right)$

情形2：$G-S$ 没有非平凡连通分支。

此时$2s+1\le i\le 2s=2$ ，若$i\ge 2s+3$ ，在$I\left(G-S\right)$ 中任选两个点添加一条边得到的图定义为$G_2$ ，则$i\left(G_2-S\right)\ge 2s+1$ ，由引理2.1此时$G_2$ 中不含$P_{\ge 2}$ -因子，即$G_2\in \Im$ 。并且$G_2-S$ 只有一个非平凡连通分支，由情况一得${\lambda }_1\left(G\right)={\rho }_1<\theta \left(n\right)$ ，矛盾。进一步可得点集$S$ 中的所有点均要与$I\left(G-S\right)$ 中的所有点相邻，所以$G\cong K_s\vee i{K}_1$ (如图2所示)。

Figure 2. $K_s\vee i{K}_1$

图2. 图$K_s\vee i{K}_1$

情形2.1：当$i=2s+1$ 时。

此时$n=3s+1$ ，$G\cong K_s\vee \left(2s+1\right)K_1$ 。考虑$V\left(G\right)$ 的一个划分：$S\cup I\left(G-S\right)$ ，则$A\left(G\right)$ 在该划分下对应的商矩阵为

$M_2=\left(\begin{array}{cc}s-1& 2s+1\\ s& 0\end{array}\right),$

令$f_2\left(x\right)$ 为$M_2$ 对应的特征方程，则

$f_2\left(x\right)=x^2-\left(s-1\right)x-s\left(2s+1\right).$

设${\rho }_2$ 为$f_2\left(x\right)=0$ 的最大根，由于该点集划分是公平划分，由引理2.4得

${\lambda }_1\left(G\right)={\rho }_2=\frac{s+\sqrt{9s^2+2s+1}-1}{2}>\frac{3}{2}s.$

若$s=1$ ，则$n=4$ ，${\rho }_2=\theta \left(4\right)=\sqrt{3}$ 。若$s=2$ ，则$n=7$ ，${\rho }_2=\frac{1+\sqrt{41}}{2}>\theta \left(7\right)=3.273$ 。若$s=3$ ，则$n=10$ ，此时${\rho }_2=1+\sqrt{22}<\theta \left(10\right)=6.075$ 。现考虑$s\ge 4$ ，此时

$f\left(x\right)=x^3-\left(3s-4\right)x^2-3sx+9s-12.$

令$h\left(s\right)=s^3-\frac{5}{2}{s}^2-6s+8$ ，由$h^{\prime }\left(s\right)=3s^2-5s-6>0$ ，得$h\left(s\right)\ge h\left(4\right)=8$ ，则

$\begin{array}{c}f\left({\rho }_2\right)-{\rho }_2{f}_2\left({\rho }_2\right)=\left(3-2s\right){\rho }_2^2+2s\left(s-1\right){\rho }_2+9s-12\\ <\frac{9}{4}\left(3-2s\right)s^2+3s^2\left(s-1\right)+9s-12\\ =-\frac{3}{2}\left(s^3-\frac{5}{2}{s}^2-6s+8\right)\\ <0.\end{array}$

所以当$s\ge 4$ 时，$f\left({\rho }_2\right)<0$ 且${\lambda }_1\left(G\right)={\rho }_2<\theta \left(n\right)$ ，矛盾。由此可推出当$i=2s+1$ 时，若$s=2$ ，$n=7$ ，则$G\cong K_2\vee 5K_1$ 。否则$G\cong K_1\vee \left(K_{n-4}\cup 3K_1\right)$ 。

情形2.2：当$i=2s+2$ 时。

此时$n=3s+2$ ，$G\cong K_s\vee \left(2s+2\right)K_1$ 。考虑$V\left(G\right)$ 的一个划分：$S\cup I\left(G-S\right)$ ，则$A\left(G\right)$ 在该划分下的商矩阵为：

$M_3=\left(\begin{array}{cc}s-1& 2s+2\\ s& 0\end{array}\right),$

令$f_3\left(x\right)$ 为$M_3$ 对应的特征方程，则

$f_3\left(x\right)=x^2-\left(s-1\right)x-2s\left(s+1\right).$

设${\rho }_3$ 为$f_3\left(x\right)=0$ 的最大根，由于该点集划分是公平的，由引理2.4得${\lambda }_1\left(G\right)={\rho }_3=2s$ 。若$s=2$ ，则$n=5$ ，${\rho }_3=\theta \left(5\right)=2$ 。当$s\ge 2$ 时，令$d\left(s\right)=-4s^3+6s^2+7s-9$ ，由于$d^{\prime }\left(s\right)=-12s^2+12s+7<0$ 得$d\left(s\right)\le d\left(2\right)=-4\times 8+6\times 4+14-9=-3<0$ ，则

$\begin{array}{c}f\left({\rho }_3\right)=8s^3-4s^2\left(3s-3\right)-2\left(3s+1\right)s+9s-9\\ =-4s^3+6s^2+7s-9\\ <0.\end{array}$

所以当$s\ge 1$ 时，$f\left({\rho }_3\right)<0$ 且${\lambda }_1\left(G\right)={\rho }_3<\theta \left(n\right)$ ，与图$G$ 的谱半径最大矛盾，所以可以推出在该种情况下$G\cong K_1\vee \left(K_{n-4}\cup 3K_1\right)$ 。

综上所述，当$n=7$ 时，此时在不含$P_{\ge 2}$ -因子的图类中，$G\cong K_2\vee 5K_1$ 的谱半径最大，此时的谱半径为$\frac{1+\sqrt{41}}{2}$ ；其余情况下，$G\cong K_1\vee \left(K_{n-4}\cup 3K_1\right)$ 。从而定理3.1得证。

命题3.1 若图$G$ 有一个完美分数匹配，则图$G$ 有一个$P_{\ge 2}$ -因子。

证明 设图$G$ 有一个完美分数匹配，则由引理1.5可得$i\left(G-S\right)\le \left|S\right|$ 对所有的$S\subseteq V\left(G\right)$ 均成立，由此可推出$i\left(G-S\right)\le 2\left|S\right|$ 对所有的$S\subseteq V\left(G\right)$ 均成立，则由引理1.1可得图$G$ 有一个$P_{\ge 2}$ -因子，证毕。

4. 小结

本文利用谱半径的界研究简单连通图中$P_{\ge 2}$ -因子的存在性。从因子存在性的充要条件出发，证明逆否命题，于不存在$P_{\ge 2}$ -因子的图类中找到该种图，谱半径的上界，从而确定了含有$P_{\ge 2}$ -因子的图类中谱半径的下界。除了可以利用邻接谱半径研究因子的存在性问题，还可以利用类似的思路在距离矩阵以及拉普拉斯矩阵中研究因子的存在性问题。

本文还利用图的分数匹配相关结论给出了图的分数匹配与因子存在性之间的联系。此外，图的匹配问题在实际应用中有着广泛的重要性，例如在社交网络中，匹配可以用来寻找潜在的好友关系或建立合适的社交连接；在交通规划中，匹配可以用来优化路线规划和交通流量管理。因此，研究特殊图类的匹配问题及其解决方案对于解决实际问题具有重要意义。除了可以利用谱半径研究分数匹配与$P_{\ge 2}$ -因子的存在性问题，还可以固定某一参数进行研究，如固定直径、悬挂点数、匹配数、最大度最小度等，在这些特殊图类中研究谱半径的界与分数匹配数的关系。