无符号拉普拉斯谱半径与分数完美匹配

The Signless Laplace Spectral Radius and Fractional Perfect Matching

摘要: 图G的分数完美匹配是一个函数f，为每条边从[0, 1]中赋值，使得对于任意的ν∈V(G)均有，其中τ(ν)是邻接于顶点v的所有边的集合。近年来，许多研究关注谱理论和匹配理论之间的联系，并利用无符号拉普拉斯谱半径给出了完美匹配存在的充分条件。作为这一结果的延伸，本文研究了无符号拉普拉斯谱的下界，以确保图G中存在分数完美匹配。令r(n)为方程X³+(5-3n)X²+(2n²-5n)x-2n²+10n-12=0的最大根，对于n≥4，当q₁(G)＞r(n)时，图G具有分数完美匹配，其中q₁(G)表示图G的无符号拉普拉斯谱半径。

Abstract: A fractional perfect matching of a graph G is a function f giving each edges a number [0, 1], so that for each ν∈V(G) , where τ(ν) is the set of edges incident to v. In recent years, many studies have focused on the connection between spectral theory and matching theory, and have given sufficient conditions for the existence of perfect matching using signless Laplacian spec-tral radius. As an extension of this result, in this paper, we study the lower bound on signless Lapla-cian spectrum to ensure the existence of a fractional perfect matching in graphs. Let r(n) be the largest root of equation X³+(5-3n)X²+(2n²-5n)x-2n²+10n-12=0 . For n≥4 , if q₁(G)＞r(n) , then G has a fractional perfect matching, where q₁(G) is the signless Laplacian spectral radius of the graph G.

1. 引言

本文涉及到的符号及术语均参考文献 [1]。本文我们仅考虑具有顶点集 $V\left(G\right)$ 和边集 $E\left(G\right)$ 的有限简单无向图，使得 $\left|V\left(G\right)\right|=n$ 且 $\left|E\left(G\right)\right|=e\left(G\right)$。顶点 $v\in V\left(G\right)$ 的度用 $d\left(v\right)$ 表示， $\delta \left(G\right)$ 表示G的顶点的最小度数。对于子集 $S\subseteq V\left(G\right)$， $G\left[S\right]$ 表示图G的由集合S导出的子图。 $G-S$ 表示图G删去顶点集合S后的子图。对于两个顶点不相交的图G和H， $G\cup H$ 表示G和H的并， $G\vee H$ 表示G和H的连接，连接是指在 $G\cup H$ 的基础上在G和H之间添加所有可能的边获得。团 $G\left[C\right]$ 是一个以集合C为顶点的完全图。

图G的邻接矩阵表示为 $A\left(G\right)={\left(a_{ij}\right)}_{n\times n}$，当顶点 $v_i$ 与 $v_j$ 邻接时， $a_{ij}=1$ ；否则 $a_{ij}=0$。

$D\left(G\right)=\left\{d\left(v_1\right),d\left(v_2\right),\cdots ,d\left(v_n\right)\right\}$ 表示图G的度对角矩阵。图G的无符号拉普拉斯矩阵 $Q\left(G\right)=D\left(G\right)+A\left(G\right)$。 $Q\left(G\right)$ 最大的特征根用 $q_1\left(G\right)$ 表示，这也被称为图G的无符号拉普拉斯谱半径。

图中的匹配是一组没有公共顶点的边；图G匹配数是所有匹配中最大的边数，记为 ${\alpha }^{\prime }\left(G\right)$。G中的完美匹配是覆盖所有顶点的匹配。图G的分数完美匹配是一个函数f，给每条边从[0, 1]中赋值，使得对于任意的 $v\in V\left(G\right)$ 均有 ${\displaystyle {\sum }_{e\in \tau \left(v\right)}f\left(e\right)}=1$，其中 $\tau \left(v\right)$ 邻接于顶点v的所有边的集合。图G的分数匹配数，记作 ${{\alpha }^{\prime }}_f\left(G\right)$，是所有分数匹配f中 ${\displaystyle {\sum }_{e\in E\left(G\right)}f\left(e\right)}$ 的最大值。

对于任意图G中分数完全匹配的存在性，Tutte首先提供了关于奇连通分支的充分必要条件 [2]。受Tutte 1-因子定理的启发，许多研究人员开始研究特征值与图中是否存在完美匹配之间的关系。例如，Chang在2003年分别研究了具有完美匹配的树和单环图的最大特征值 [3] [4]。不久之后，Brouwer和Haemers根据拉普拉斯矩阵的特征值发现了图中存在完美匹配的充分条件 [5]。2005年，Cioabă [6] 改进了Brouwer和Haemers的结果。此外，Cioabă等人给出了第三大特征值的上限 [7]，以确保图G在n为偶数时存在完美匹配，在n为奇数时存在一个大小为 $n-1$ 的匹配，其中G是连通的r-正则图。2016年，O研究了图中的谱半径和分数匹配之间的关系 [8]。最近，O建立了谱半径和一般图中的匹配数之间的联系 [9]。Pan等人在2020年进一步研究了图中的分数匹配 [10]。Liu等人结合文献 [9]，建立了无符号拉普拉斯谱半径和完美匹配之间的一些性质 [11]。作为上述这些结果的延伸，本文我们研究了无符号拉普拉斯谱的下界，以确保图G中存在分数完美匹配。

图的分数完美匹配理论广泛应用于网络设计、组合拓扑、设计决策列表等多个研究领域。例如，在通信网络中，如果我们允许将大数据进行拆分成多个小数据包在网络上传输，这些小数据包将通过不同的路径传输到不同的目标节点。那么这种方法将有效地提高传输效率。这种有效可行的数据包分配问题就是找到满足某些特殊条件的部分完美匹配。

2. 预备知识

定义1 [12] 令M为 $n\times n$ 阶的实对称矩阵，其行和列由 $\left\{Y_1,Y_2,\cdots ,Y_m\right\}$ 所表示，其中 $\left\{Y_1,Y_2,\cdots ,Y_m\right\}$ 是关于顶点 $\left\{1,2,\cdots ,n\right\}$ 的一个划分。

$\left(\begin{array}{cccc}{M}_{1,1}& M_{1,2}& \cdots & M_{1,m}\\ M_{2,1}& M_{2,2}& \cdots & M_{2,m}\\ ⋮& ⋮& \ddots & ⋮\\ M_{m,1}& M_{m,2}& \cdots & M_{m,m}\end{array}\right)$

其行和列被划分为 $\left\{Y_1,Y_2,\cdots ,Y_m\right\}$。商矩阵R是 $m\times m$ 阶矩阵，其各位置元素是M的块 $M_{ij}$ 的平均行和。如果M的每个块 $M_{ij}$ 具有恒定的行总和，则划分是公平的，此时称R为等商矩阵。

引理1 [13] 图G包含一个分数完美匹配当且仅当对于任意顶点子集 $S\subseteq V\left(G\right)$，有 $i\left(G-S\right)\le \left|S\right|$ 成立，其中 $i\left(G-S\right)$ 表示图 $G-S$ 中孤立点的数目。

引理2 [14] 令R为对应于给定划分的对称矩阵M的商矩阵。则R的特征值与M的特征值交错。如果交错紧密，则划分是公平的。

引理3 [15] 令M为划分公平矩阵，R为其等商矩阵。那么商矩阵R的特征值就是M的特征值。另外，如果M是一个非负矩阵，那么商矩阵R的谱半径等于M的谱半径。

令 $A={\left(a_{ij}\right)}_{n\times n}$， $B={\left(b_{ij}\right)}_{n\times n}$，定义 $A\le B$，如果对于任意的 $i,j$ 有 $a_{ij}\le b_{ij}$ ； $A<B$，如果对于任意的 $i,j$

有 $a_{ij}<b_{ij}$。

引理4 [16] 令 $A={\left(a_{ij}\right)}_{n\times n}$， $B={\left(b_{ij}\right)}_{n\times n}$ 是两个谱半径分别为 ${\lambda }_1\left(A\right)$ 、 ${\lambda }_1\left(B\right)$ 的矩阵。如果 $0\le A\le B$，

则 ${\lambda }_1\left(A\right)\le {\lambda }_1\left(B\right)$。更进一步，如果 $0\le A<B$，则 ${\lambda }_1\left(A\right)<{\lambda }_1\left(B\right)$。

定理1 令G为n顶点连通图。对于 $n\ge 4$，如果 $q_1\left(G\right)>r\left(n\right)$，其中 $r\left(n\right)$ 为方程 $x^3+\left(5-3n\right)x^2+\left(2n^2-5n\right)x-2n^2+10n-12=0$ 的最大根，则G具有分数完美匹配。

定理2 如果G是一个n顶点连通图，当 $\left|E\left(G\right)\right|>\left(n^2-3n+4\right)/2$ 时，图G包含一个分数完美匹配。

3. 定理1的证明

在本节中，我们将使用商矩阵的相关性质和分数Tutte 1-因子定理来证明定理1。

证明假设图G不含有分数完美匹配，根据引理1，存在一个顶点子集 $S\subseteq V\left(G\right)$，使得 $i\left(G-S\right)>\left|S\right|$。令 $k=i\left(G-S\right)$，则 $k\ge \left|S\right|+1$。

第一步，我们通过以下步骤在图G的基础上构造图 $G^{\prime }$ ：1) 在S的所有分支中添加边，使得 $G\left[S\right]$ 成为一个团；2) 分别将 $G-S$ 和S中每个分支中的所有孤立顶点做连接。需要指出的是，我们将孤立顶点也视为一个分支。

令 $\left\{S,V\left(G_1\right),V\left(G_2\right),\cdots ,V\left(G_k\right),V\left(G_{k+1}\right)\right\}$ 为顶 $V\left(G\right)$ 的划分，且

$\left|V\left(G_1\right)\right|\ge \left|V\left(G_2\right)\right|=\cdots =\left|V\left(G_k\right)\right|=\left|V\left(G_{k+1}\right)\right|=1$。因此 $n_1\ge n_2=\cdots =n_k=n_{k+1}=1,n=s+n_1+n_2+\cdots +n_k+n_{k+1}$。其中 $s=\left|S\right|$， $n_i=\left|V\left(G_i\right)\right|$。由引理4知 $q_1\left(G\right)\le q_1\left(G^{\prime }\right)$。 $Q\left(G^{\prime }\right)$ 对应的商矩阵 $C_1$ 为

$C_1=\left(\begin{array}{ccccc}n+s-2& n-s-k& \cdots & 1& 1\\ s& 2n_1+s-2& \cdots & 0& 0\\ ⋮& ⋮& \ddots & ⋮& ⋮\\ s& 0& \cdots & s& 0\\ s& 0& \cdots & 0& s\end{array}\right)$

通过计算，我们可以得到 $C_1$ 的特征多项式，即：

$\begin{array}{c}{f}_1\left(x\right)=\left(x-n-s+2\right)\left(x-2n_1-s+2\right){\left(x-s\right)}^k-s\left(n-s-k\right){\left(x-s\right)}^k\\ +s\left(x-2n_1-s+2\right){\left(x-s\right)}^k+{\left(-1\right)}^{i}s\left(x-2n_1-s+2\right){\left(x-s\right)}^{k-1}\\ +\cdots +{\left(-1\right)}^{k+1}s\left(x-2n_1-s+2\right){\left(x-s\right)}^{k-1}\end{array}$

结合引理2，有 $r_f=q_1\left(G^{\prime }\right)$，其中 $r_f$ 是方程 $f_1\left(x\right)=0$ 的最大根。

第二步，我们考虑一个新的图 $G^{″}$，它是通过以下方式从 $G^{\prime }$ 得到的：1) 删除 $G_1$ 中的一个顶点，并在 $G_{k+1}$ 中添加一个顶点，然后我们得到两个新的分支 ${G^{\prime }}_1$ 和 ${G^{\prime }}_{k+1}$ ；2) 添加边使得 ${G^{\prime }}_{k+1}$ 变成团；3) 连接 ${G^{\prime }}_{k+1}$ 和S。

显然， ${n^{\prime }}_{k+1}=\left|V\left({G^{\prime }}_{k+1}\right)\right|=n_{k+1}+1$， ${n^{\prime }}_1=\left|V\left({G^{\prime }}_1\right)\right|=n_1-1$。需要指出 $G^{″}-S$ 和 $G\left[S\right]$ 均为团。利用新的划分 $\left\{S,V\left({G^{\prime }}_1\right),V\left(G_2\right),\cdots ,V\left(G_k\right),V\left({G^{\prime }}_{k+1}\right)\right\}$，得到关于 $Q\left(G^{″}\right)$ 的商矩阵 $C_2$ ：

$C_2=\left(\begin{array}{ccccc}n+s-2& n_1-1& \cdots & 1& 2\\ s& 2n_1+s-4& \cdots & 0& 0\\ ⋮& ⋮& \ddots & ⋮& ⋮\\ s& 0& \cdots & s& 0\\ s& 0& \cdots & 0& s+2\end{array}\right)$

通过计算，我们可以得到 $C_2$ 的特征多项式，即：

$\begin{array}{c}{f}_2\left(x\right)=\left(x-n-s+2\right)\left(x-2n_1-s-4\right){\left(x-s\right)}^{k-1}\left(x-s-2\right)-s\left(n_1-1\right){\left(x-s\right)}^{k-1}\left(x-s-2\right)\\ +s\left(x-2n_1-s+4\right){\left(x-s\right)}^{k-1}\left(x-s-2\right)+{\left(-1\right)}^{i}s\left(x-2n_1-s+4\right){\left(x-s\right)}^{k-1}\left(x-s-2\right)\\ +\cdots +{\left(-1\right)}^{k+1}s\left(x-2n_1-s+4\right){\left(x-s\right)}^{k-1}\left(x-s-2\right)\end{array}$

将 $r_f$ 的值代入 $f_2\left(x\right)$，由于 $f_1\left(r_f\right)=0$，那么我们有 $f_2\left(r_f\right)<0$，这意味着 $r_f<{r^{\prime }}_f$，其中 ${r^{\prime }}_f$ 是 $f_2\left(x\right)=0$ 的最大根。由于 $C_2$ 是 $G^{″}$ 的等商矩阵，因此 $q_1\left(G^{\prime }\right)<q_1\left(G^{″}\right)$。

根据上述过程，我们可以得知当 $n_1=n-s-k$， $n_i=1,2\le i\le k+1$ 时，图 $G^{\prime }$ 存在最大的谱半径。由此，利用图 $G^{\prime }$ 中新的划分 $\left\{V\left(G_1\right),S,V\left(G\right)-S-V\left(G_1\right)\right\}$，得到关于 $Q\left(G^{\prime }\right)$ 的商矩阵 $C_3$ ：

$C_3=\left(\begin{array}{ccc}2n_1+s-2& s& 0\\ n_1& n+s-2& k\\ 0& s& s\end{array}\right)$

通过计算，我们可以很容易得到 $C_3$ 的特征多项式为:

$f_3\left(x\right)=\left(x-2n_1-s+2\right)\left[\left(x-n-s+2\right)\left(x-s\right)-sk\right]-n_{1}s\left(x-s\right)$。

接下来，我们通过以下方式从 $G^{\prime }$ 中构造一个新图 $G^{‴}$ ：1) 删除一个分支 $G_k$，并在 $G_1$ 中添加一个顶点，然后我们到一个新分支 $G^{″}$ ；2) 添加边以使 ${G^{″}}_1$ 成为团；3) 连接 ${G^{″}}_1$ 和S。这里 $G^{‴}-S$ 以及 $G\left[S\right]$ 是团，且 $G^{‴}-S$ 只有k个分支。类似的， $Q\left(G^{‴}\right)$ 的商矩阵 $C_4$ ：

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

其特征多项式为：

$\begin{array}{c}{f}_4\left(x\right)=\left(x-2n_1-s+2\right)\left[\left(x-n-s+2\right)\left(x-s\right)-s\left(k-1\right)\right]-\left(n_1+1\right)s\left(x-s\right)\\ =\left(x-2n_1-s+2\right)\left[\left(x-n-s+2\right)\left(x-s\right)-sk\right]-n_{1}s\left(x-s\right)-s\left(x-s\right)\\ -2\left[\left(x-n-s+2\right)\left(x-s\right)-sk+s\right]+s\left(x-2n_1+2\right)\\ =f_3\left(x\right)-s\left(x-s\right)-2\left[\left(x-n-s+2\right)\left(x-s\right)-sk+s\right]+s\left(x-2n_1+2\right)\end{array}$

令 $r_{f_3}$ 是 $f_3\left(x\right)=0$ 的最大根。因此

$f_4\left(r_{f_3}\right)=-s\left(r_{f_3}-s\right)-2\left[\left(r_{f_3}-n-s+2\right)\left(r_{f_3}-s\right)-sk+s\right]+s\left(r_{f_3}-2n_1+2\right)<0$。

这意味着 $r_{f_3}<r_{f_4}$，其中 $r_{f_4}$ 是 $f_4\left(x\right)=0$ 的最大根。易知 $q_1\left(G^{\prime }\right)<q_1\left(G^{‴}\right)$。

根据上述过程，我们可以得知当 $k=s+1$ 时图 $G^{\prime }$ 存在最大的谱半径。由此，利用图 $G^{\prime }$ 中新的划分 $\left\{V\left(G_1\right),S,V\left(G\right)-S-V\left(G_1\right)\right\}$，得到关于 $Q\left(G^{\prime }\right)$ 的商矩阵 $C_5$ ：

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

通过计算，我们可以很容易得到 $C_5$ 的特征多项式为：

$\begin{array}{c}{f}_4\left(x\right)=\left(x-2n_1-s+2\right)\left[\left(x-n-s+2\right)\left(x-s\right)-s^2\right]-\left(n_1+1\right)s\left(x-s\right)\\ =x^3+\left(-3n+s+6\right)x^2+\left(2n^2+ns-8n-4s^2-4s+8\right)x\\ -2n^2+4n{s}^2+8ns-2s^3-6s^2-8s\end{array}$

类似于Zhao等人在文献 [17] 中的方法可知当 $s=1$ 时便有我们的定理1成立。

4. 定理2的证明

根据定理1的证明过程，我们可以使用极值图 $K_1\vee \left(K_{n-2}\cup K_1\right)$ 来保证就图的边数而言的分数完美匹配的存在性。

证明假设图G不含有分数完美匹配，根据引理1，存在一个顶点子集 $S\subseteq V\left(G\right)$，使得 $i\left(G-S\right)>\left|S\right|$。令 $k=i\left(G-S\right)$，则 $k\ge \left|S\right|+1$。

为了找到最大的无符号拉普拉斯谱半径，我们在图G的基础上通过如下步骤构造图 $G^{\prime }$ ：1) 在S的所有分支中添加边，使得 $G\left[S\right]$ 成为一个团；2) 分别将 $G-S$ 和S中每个分支中的所有孤立顶点做连接。因此有 $\left|E\left(G\right)\right|\le \left|E\left(G^{\prime }\right)\right|$。

令 $G_1,G_2,\cdots ,G_k,G_{k+1}$ 为 $G^{\prime }-S$ 的分支，使得 $\left|V\left(G_1\right)\right|\ge \left|V\left(G_2\right)\right|=\cdots =\left|V\left(G_k\right)\right|=\left|V\left(G_{k+1}\right)\right|=1$。我们通过在 $G^{\prime }$ 的基础上删除 $G_1$ 中的一个顶点，在 $G_{k+1}$ 中增加一个顶点，并与分支 $G_{k+1}$ 和S做连接，使得 $G^{″}-S$ 和 $G\left[S\right]$ 是团。然后我们有

$\left|E\left(G^{″}\right)\right|=\left|E\left(G^{\prime }\right)\right|+1>\left|E\left(G^{\prime }\right)\right|\ge \left|E\left(G\right)\right|$

这意味着当 $k=s+1$ (或者 $\left|V\left(G_1\right)\right|=n-2s-1$ )时， $G^{\prime }$ 有最大的边数。

需要指出 $n\ge 2s+1+n_1$，其中 $n_1\ge 1$。我们将 $G^{\prime }$ 与 $H_n=K_1\vee \left(K_{n-2}\cup K_1\right)$ 中的边数作对比，即有：

$\begin{array}{c}\left|E\left(H_n\right)\right|-\left|E\left(G^{\prime }\right)\right|=\left(\begin{array}{c}n-2\\ 2\end{array}\right)+n-1-\left(\begin{array}{c}n-s-1\\ 2\end{array}\right)-s^2\\ =\frac{\left(n-2\right)\left(n-3\right)+2\left(n-1\right)}{2}-\frac{\left(n-s-1\right)\left(n-s-2\right)}{2}-s^2\\ =\frac{2+2ns-3s-3s^2}{2}\end{array}$

当 $2+2ns-3s-3s^2\ge 0$ 时，有 $\left|E\left(H_n\right)\right|\ge \left|E\left(G^{\prime }\right)\right|$，因此结论得证。

NOTES

^*通讯作者。