DOI:10.12677/PM.2023.131007,PDF,HTML,XML,被引量下载: 372浏览: 616科研立项经费支持
作者:李 振,章 超^*：贵州大学，数学与统计学院，贵州 贵阳
关键词:k-匹配理论；谱半径；商矩阵；k-Matching Theory；Spectral Radius；Quotient Matrix

文章引用：李振, 章超. 图的A _α-谱半径与k-匹配数[J]. 理论数学, 2023, 13(1): 67-73. https://doi.org/10.12677/PM.2023.131007

1. 引言

在本文中，我们只考虑无向简单图。设 $G=\left(V\left(G\right),E\left(G\right)\right)$是一个图， $G\left(V\right)$和 $G\left(E\right)$分别表示图中的顶点集和边集。除非另有规定，我们均使用文献 [1] 中的以下符号和定义。

我们将 $N\left(v\right)$表示为顶点v的一组邻接顶点，并用 $d\left(v\right)=\left|N\left(v\right)\right|$表示v的度。设 $\delta$和 $\Delta$分别为图的最小度和最大度。零度顶点也被称为孤立顶点。我们用 $odd\left(G\right)$表示奇分量的集合，其阶数至少为3，用 $m=\left|odd\left(G\right)\right|$表示奇分量的数量，用 $i\left(G\right)$代表G中孤立顶点的数量。图G的邻接矩阵定义为 $A\left(G\right)={\left(a_{ij}\right)}_{n\times n}$，如果顶点i和j相邻，则 $a_{ij}=1$，否则 $a_{ij}=0$。令 $D\left(G\right)$表示图G关于顶点度的对角矩阵。 $L\left(G\right)=D\left(G\right)-A\left(G\right)$和 $Q\left(G\right)=D\left(G\right)+A\left(G\right)$分别称为图G的拉普拉斯矩阵和无符号拉普拉斯矩阵。对于任意 $\alpha \in \left[0,1\right)$，Nikiforov [2] 引入图G的 $A_{\alpha }$-矩阵为 $A_{\alpha }\left(G\right)=\alpha D\left(G\right)+\left(1-\alpha \right)A\left(G\right)$。需要指出的是， $A_0=A\left(G\right)$， $A_{\frac{1}{2}}=\frac{1}{2}Q\left(G\right)$。 $A\left(G\right)$的最大特征值称为图G的谱半径，拉普拉斯谱半径和无符号拉普拉斯谱半径也可以类似地定义。

现在我们回顾文献 [3] 中k-匹配的定义，这是整数匹配的自然推广。设k为整数，图G的k-匹配是函数 $f:E\left(G\right)\to \left\{0,1,\cdots ,k\right\}$使得对于任何顶点 $v\in v\left(G\right)$，均有 ${\displaystyle {\sum }_{e~v}f\left(e\right)}\le k$。如果对于匹配M的每个顶点v，均有 ${\displaystyle {\sum }_{e~v}f\left(e\right)}=k$，则匹配M称为G的完美k-匹配。图G的k-匹配数用 ${\mu }_k\left(G\right)$表示，是所有k-匹配f上使得 ${\displaystyle {\sum }_{e\in E\left(G\right)}f\left(e\right)}$为最大值时的k-匹配。很容易知道，当 $k=1$时，完美1-匹配是我们熟悉的整数类型的完美匹配。根据文献 [4]，我们知道当 $k=2$时，完美2-匹配相当于分数完美匹配。图的k-匹配被广泛应用于网络设计、组合拓扑等许多研究领域。

近年来，图是否能为某些性质找到谱充分条件的问题越来越受到人们的关注，特别是在研究图的特征值与匹配数之间的关系方面。例如，当k为偶数时，Y. Liu和X. Liu [5] 证明了图的整数k-匹配数等于其分数匹配数的k倍，其中分数匹配是通过使用Pulleyblank [6] 给出的生成特殊分数匹配的算法，将整数匹配中的赋值集{0, 1}替换为实数集[0, 1]来定义的。H. Lu和W. Wang [7] 研究了一般图的完美k-匹配，并给出了当k为奇数时其存在的充分必要条件。最近，Y. Liu，X. Su，D. Xiong [3] 研究了当k为奇数时，图中k-匹配的数量。这一结果与文献 [7] 中的Berge-Tutte公式非常相似。此外，在文献 [8] 中，R. F. Liu等人从最小度 $\delta$的角度探讨了分数匹配数与谱半径之间的关系。

在本文中，我们主要研究k-匹配数与谱半径相对于奇分量的数量之间的关系(见定理3.1)。

2. 预备知识

在本节中，我们将介绍完美k-匹配的一些特征和一些引理。

令M为n × n阶的实对称矩阵，设M是n阶对称实矩阵，描述为如下形式

$M=\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)$

其中块 $M_{ij}$是任意 $1\le i,j\le m$且 $n=n_1+\cdots +n_m$的 $n_i\times n_j$矩阵。对于 $1\le i,j\le m$，令 $b_{ij}$表示 $M_{ij}$的平均行和，即 $b_{ij}$是 $M_{ij}$中所有条目的和除以行数。 $B=\left(b_{ij}\right)$被称为M的商矩阵。此外，如果M的每个块 $M_{ij}$具有恒定的行和，则B被称为M的公平商矩阵。

对于任何非负矩阵M，我们用 $\rho \left(M\right)$表示M的谱半径。我们有如下关于公平商矩阵的引理。

引理2.1 [9] [10] 设M，M₁，M₂是非负矩阵。然后

1) 如果B是M的公平商矩阵，那么B的特征值也是M的特征值，并且 $\rho \left(M\right)=\rho \left(B\right)$。

2) 如果 $M_1-M_2$为非负，则 $\rho \left(M_1\right)\ge \rho \left(M_2\right)$。

对于k-匹配，我们有以下结果。

命题2.2设G是连通图，f是G上的k-匹配。则 ${\displaystyle {\sum }_{e\in E\left(G\right)}f\left(e\right)}\le \frac{1}{2}k\left|V\left(G\right)\right|$，当且仅当f是完美k-匹配时等式成立。因此，k-匹配数 ${\mu }_k\left(G\right)\le \frac{1}{2}k\left|V\left(G\right)\right|$，等式成立当且仅当图G存在完美k-匹配。

证明：对于任何顶点v和k匹配的f，我们有 ${\displaystyle {\sum }_{e~v}f\left(e\right)}\le k$。对所有顶点v将这些不等式求和，我们有 $\frac{1}{k}{\displaystyle {\sum }_{e\in E\left(G\right)}2f\left(e\right)}\le \left|v\left(G\right)\right|$。

因此，我们获得了期望的结果。根据k-匹配数的定义，我们可以很容易地知道f是G上的完美k-匹配，当且仅当 ${\displaystyle {\sum }_{e\in E\left(G\right)}f\left(e\right)}\le \frac{1}{2}k\left|v\left(G\right)\right|$。

文献 [3] 中的以下命题为我们提供了完美k-匹配存在的标准。

命题2.3设G为图。

1) 如果 $k\ge 2$是偶数，则对于所有 $S\subseteq V\left(G\right)$，G具有完美k-匹配当且仅当 $i\left(G-S\right)\le \left|S\right|$。

2) 如果 $k\ge 1$是奇数，则对于所有子集 $S\subseteq V\left(G\right)$，G具有完美k-匹配当且仅当 $odd\left(G-S\right)+ki\left(G-S\right)\le k\left|S\right|$。

引理2.4 (k-Berge-Tutte formula, [11] )对于任意图G，

${\mu }_k\left(G\right)=\frac{1}{2}\left(k\left|V\left(G\right)\right|-\max \left\{odd\left(G-S\right)+ki\left(G-S\right)-k\left|S\right||S\subset V\left(G\right)\right\}\right).$

引理2.5 [12] 设G是具有n个顶点的连通图，如果 $\left|E\left(G\right)\right|\ge C_{n-1}^2+1$，则G包含哈密顿路。

3. 主要结论

定理3.1设G是 $n=\left|V\left(G\right)\right|$且 $\delta =\delta \left(G\right)$的连通图，且 $\alpha \in \left[0,1\right)$是实数且 $k>m$。如果

${\lambda }_1\left(\alpha D\left(G\right)+\left(1-\alpha \right)A\left(G\right)\right)<\{\begin{array}{l}\delta \sqrt{1+\frac{2\left(1-\frac{m}{k}\right)}{n-\left(3m+1-\frac{m}{k}\right)}},\alpha =0\\ \frac{2\alpha \delta }{1-\alpha }\left[\frac{n-3m}{n-\left(3m+1-\frac{m}{k}\right)}\right],\alpha \in \left(0,\frac{1}{2}\right]\\ \frac{\alpha \delta }{1-\alpha }\left[1+\frac{2\left(1-\frac{m}{k}\right)}{n-\left(3m+1-\frac{m}{k}\right)}\right],\alpha \in \left(\frac{1}{2},1\right)\end{array}$

则 ${\mu }_k\left(G\right)>\frac{kn-\left(1-\frac{m}{k}\right)}{2}$。

证明：采用反证法证明，假设 ${\mu }_k\left(G\right)\le \frac{kn-\left(1-\frac{m}{k}\right)}{2}$，因此 ${\mu }_k\left(G\right)<\frac{kn}{2}$。这意味着图G不具有命题2.2的完美k-匹配。因此，根据命题2.3，存在满足 $i\left(G-S\right)-\left|S\right|\ge 1-\frac{m}{k}$的顶点子集 $S\subseteq V\left(G\right)$。设T是 $G-S$中的孤立顶点集， $\left|S\right|=s$， $\left|T\right|=t$。则 $3m+s+t\le n$， $t=i\left(G-S\right)\ge S+1-\frac{m}{k}$，因此 $S\le \frac{n-\left(3m+1-\frac{m}{k}\right)}{2}$。由于T是 $G-S$中孤立顶点的集合，我们观察到 $N_G\left(T\right)\subseteq S$，因此 $S\ge \delta$。

设 $X=E_G\left[S,T\right]$， $H=G\left[X\right]$是由X诱导的二部图G，并且 $r=\left|E\left(H\right)\right|$。则 $r\ge t\delta$。因此， $\alpha D\left(H\right)+\left(1-\alpha \right)A\left(H\right)$相对于分区 $\left(S,T\right)$的商矩阵 $R\left(\alpha D\left(H\right)+\left(1-\alpha \right)A\right)$：

$R\left(\alpha D\left(H\right)+\left(1-\alpha \right)A\left(H\right)\right)=\left(\begin{array}{cc}\frac{\alpha r}{s}& \frac{\left(1-\alpha \right)r}{s}\\ \frac{\left(1-\alpha \right)r}{t}& \frac{\alpha r}{t}\end{array}\right)$

$R\left(\alpha D\left(H\right)+\left(1-\alpha \right)A\left(H\right)\right)$的特征多项式为： ${\lambda }^2-\alpha \left(\frac{r}{s}+\frac{r}{t}\right)\lambda +\left[{\alpha }^2-{\left(1-\alpha \right)}^2\right]\frac{r^2}{st}=0$，直接计算便有：

$\begin{array}{c}{\lambda }_1\left(\alpha D\left(H\right)+\left(1-\alpha \right)A\left(H\right)\right)=\frac{1}{2}\left\{\alpha \left(\frac{r}{s}+\frac{r}{t}\right)+\sqrt{{\alpha }^2{\left(\frac{r}{s}+\frac{r}{t}\right)}^2-4\left[{\alpha }^2-{\left(1-\alpha \right)}^2\right]\frac{r^2}{st}}\right\}\\ =\frac{1-\alpha }{2}\left\{\frac{\alpha }{1-\alpha }\left(\frac{r}{s}+\frac{r}{t}\right)+\sqrt{\left[{\left(\frac{\alpha }{1-\alpha }\right)}^2-1\right]{\left(\frac{r}{s}-\frac{r}{t}\right)}^2+{\left(\frac{r}{s}+\frac{r}{t}\right)}^2}\right\}\end{array}$

情况1：当 $\alpha =0$时， ${\lambda }_1\left(\alpha D\left(H\right)+\left(1-\alpha \right)A\left(H\right)\right)=r\sqrt{\frac{1}{st}}$。因此，

$\begin{array}{c}{\lambda }_1\left(\alpha D\left(G\right)+\left(1-\alpha \right)A\left(G\right)\right)\ge {\lambda }_1\left(\alpha D\left(H\cup \left(n-s-t\right)K_1\right)+\left(1-\alpha \right)A\left(H\cup \left(n-s-t\right)K_1\right)\right)\\ ={\lambda }_1\left(\alpha D\left(H\right)+\left(1-\alpha \right)A\left(H\right)\right)\ge {\lambda }_1\left(R\left(\alpha D\left(H\right)+\left(1-\alpha \right)A\left(H\right)\right)\right)\\ =r\sqrt{\frac{1}{st}}\ge \delta \sqrt{\frac{t}{s}}\ge \delta \sqrt{1+\frac{k-m}{sk}}\ge \delta \sqrt{1+\frac{2\left(1-\frac{m}{k}\right)}{n-\left(3m+1-\frac{m}{k}\right)}}\end{array}$

情况2：当 $0<\alpha <\frac{1}{2}$时， ${\left(\frac{\alpha }{1-\alpha }\right)}^2-1\le 0$，由此可知：

$\begin{array}{c}{\lambda }_1\left(R\left(\alpha D\left(H\right)+\left(1-\alpha \right)A\left(H\right)\right)\right)\ge \frac{1-\alpha }{2}\left\{\frac{\alpha }{1-\alpha }\left(\frac{r}{s}+\frac{r}{t}\right)+\sqrt{\left[{\left(\frac{\alpha }{1-\alpha }\right)}^2-1\right]{\left(\frac{r}{s}-\frac{r}{t}\right)}^2+{\left(\frac{r}{s}+\frac{r}{t}\right)}^2}\right\}\\ =\frac{\alpha }{1-\alpha }\left(\frac{r}{s}+\frac{r}{t}\right)\end{array}$

据此有，

$\begin{array}{c}{\lambda }_1\left(\alpha D\left(G\right)+\left(1-\alpha \right)A\left(G\right)\right)\ge {\lambda }_1\left(\alpha D\left(H\right)+\left(1-\alpha \right)A\left(H\right)\right)\ge {\lambda }_1\left(R\left(\alpha D\left(H\right)+\left(1-\alpha \right)A\left(H\right)\right)\right)\\ \ge \frac{\alpha }{1-\alpha }\left(\frac{r}{s}+\frac{r}{t}\right)\ge \frac{\alpha }{1-\alpha }\delta \left(1+\frac{t}{s}\right)\ge \frac{\alpha \delta }{1-\alpha }\left(2+\frac{1-\frac{m}{k}}{s}\right)\\ \ge \frac{\alpha \delta }{1-\alpha }\left[2+\frac{2\left(1-\frac{m}{k}\right)}{n-\left(3m+1-\frac{m}{k}\right)}\right]=\frac{2\alpha \delta }{1-\alpha }\left[\frac{n-3m}{n-\left(3m+1-\frac{m}{k}\right)}\right]\end{array}$

情况3：当 $\frac{1}{2}<\alpha <1$时， ${\left(\frac{\alpha }{1-\alpha }\right)}^2-1>0$，由此可知：

$\begin{array}{c}{\lambda }_1\left(R\left(\alpha D\left(H\right)+\left(1-\alpha \right)A\left(H\right)\right)\right)>\frac{1-\alpha }{2}\left\{\frac{\alpha }{1-\alpha }\left(\frac{r}{s}+\frac{r}{t}\right)+\sqrt{\left[{\left(\frac{\alpha }{1-\alpha }\right)}^2-1\right]{\left(\frac{r}{s}-\frac{r}{t}\right)}^2+{\left(\frac{r}{s}+\frac{r}{t}\right)}^2}\right\}\\ =\left(\frac{\alpha }{1-\alpha }\right)\frac{r}{s}\end{array}$

据此有，

$\begin{array}{c}{\lambda }_1\left(\alpha D\left(G\right)+\left(1-\alpha \right)A\left(G\right)\right)\ge {\lambda }_1\left(\alpha D\left(H\right)+\left(1-\alpha \right)A\left(H\right)\right)\ge {\lambda }_1\left(R\left(\alpha D\left(H\right)+\left(1-\alpha \right)A\left(H\right)\right)\right)\\ \ge \left(\frac{\alpha }{1-\alpha }\right)\frac{r}{s}\ge \left(\frac{\alpha \delta }{1-\alpha }\right)\frac{t}{s}\ge \frac{\alpha \delta }{1-\alpha }\left(1+\frac{1-\frac{m}{k}}{s}\right)\\ \ge \frac{\alpha \delta }{1-\alpha }\left[1+\frac{2\left(1-\frac{m}{k}\right)}{n-\left(3m+1-\frac{m}{k}\right)}\right]\end{array}$

定理3.2设G是 $n=\left|V\left(G\right)\right|$且 $\delta =\delta \left(G\right)$的连通图，且 $\alpha \in \left[0,1\right)$是实数且 $k>m$。如果

${\lambda }_1\left(\alpha D\left(\bar{G}\right)+\left(1-\alpha \right)A\left(\bar{G}\right)\right)<\delta -\frac{m}{k}$

因此 ${\mu }_k\left(G\right)>\frac{kn-\left(1-\frac{m}{k}\right)}{2}$。

证明：假设 ${\mu }_k\left(G\right)\le \frac{kn-\left(1-\frac{m}{k}\right)}{2}<\frac{kn}{2}$。这意味着，图G不包含完美k-匹配。因此，根据定理2.3，存在满足 $i\left(G-S\right)-\left|S\right|\ge 1-\frac{m}{k}$的顶点子集 $S\subseteq V\left(G\right)$。设T是 $G-S$中孤立顶点的集合， $\left|S\right|=s$， $\left|T\right|=t$。那么 $t=i\left(G–S\right)\ge s+1-\frac{m}{k}$。由于T是 $G-S$中孤立点的集合，我们观察到 $N_G\left(T\right)\subseteq S$，因此 $s\ge \delta$。由于 $K_t\cup \left(n-t\right)K_1$是 $\bar{G}$的生成子图，因此

$\begin{array}{c}{\lambda }_1\left(\alpha D\left(\bar{G}\right)+\left(1-\alpha \right)A\left(\bar{G}\right)\right)\ge {\lambda }_1\left(\alpha D\left(K_t\cup \left(n-t\right)K_1\right)+\left(1-\alpha \right)A\left(K_t\cup \left(n-t\right)K_1\right)\right)\\ =t-1\ge s-\frac{m}{k}\ge \delta -\frac{m}{k}\end{array}$

这与假设矛盾。

推论3.3设 是 $n=\left|V\left(G\right)\right|$且 $\delta =\delta \left(G\right)$的连通图，且 $\alpha \in \left[0,1\right)$是实数，如果

${\lambda }_1\left(\alpha D\left(G\right)+\left(1-\alpha \right)A\left(G\right)\right)<\{\begin{array}{ll}\delta \sqrt{1+\frac{2}{n-1}},\hfill & \alpha =0\hfill \\ \left(\frac{2\alpha \delta }{1-\alpha }\right)\frac{n}{n-1},\hfill & \alpha \in \left(0,\frac{1}{2}\right]\hfill \\ \frac{\alpha \delta }{1-\alpha }\left(1+\frac{2}{n-1}\right],\hfill & \alpha \in \left(\frac{1}{2},1\right)\hfill \end{array}$

则图G包含完美k-匹配。

证明：在定理3.1中，设 $m=0$，我们可以知道 ${\mu }_k\left(G\right)>\frac{kn-1}{2}$。根据命题2.2有 ${\mu }_k\left(G\right)\le \frac{kn}{2}$，由于 ${\mu }_k\left(G\right)$是一个整数。这迫使 ${\mu }_k\left(G\right)=\frac{kn}{2}$，这意味着G包含完美k-匹配。

同样，我们可以很容易地得出以下结论：

推论3.4设G是 $n=\left|V\left(G\right)\right|$且 $\delta =\delta \left(G\right)$的连通图，且 $\alpha \in \left[0,1\right)$是实数。如果

${\lambda }_1\left(D\left(\bar{G}\right)+\left(1-\alpha \right)A\left(\bar{G}\right)\right)<\delta$

则图G包含完美k-匹配。

定理3.5设G是具有n个顶点的连通图且 $n\ge 4$，n为偶数，如果 $\left|E\left(G\right)\right|\ge C_{n-1}^2+1$，则G包含完美k-匹配。

证明：根据定理2.5，图G包含哈密顿路 $P_n$。对于任何 $e\in E\left(P_n\right)$，我们可以通过交替地将 $f\left(e\right)=k$和 $f\left(e\right)=0$赋给 $P_n$，对于 $P_n$之外的边赋值0，以此来构造完美k-匹配。

基金项目

本文由贵州省科技厅项目(批准号：黔科合基础[2020]1Y405)资助。

NOTES

^*通讯作者。

参考文献

[1]	Lovász, L. and Plummer, M.D. (1986) Matching Theory. Annals of Discrete Mathematics, 29.
[2]	Nikiforov, V. (2017) Merging the A- and Q-Spectral Theories. Applicable Analysis and Discrete Mathematics, 11, 81-107. https://doi.org/10.2298/AADM1701081N
[3]	Lu, H.L. and Wang, W. (2014) On Perfect k-Matchings. Graphs and Combinatorics, 30, 229-335. https://doi.org/10.1007/s00373-012-1259-7
[4]	Tutte, W.T. (1953) The 1-Factors of Oriented Graphs. Proceed-ings of the American Mathematical, 4, 922-931. https://doi.org/10.1090/S0002-9939-1953-0063009-7
[5]	Liu, Y. and Liu, X.H. (2018) Integer k-Matchings of Graphs. Discrete Applied Mathematics, 235, 118-128. https://doi.org/10.1016/j.dam.2017.08.013
[6]	Pulleyblank, W.R. (1987) Fractional Matching and the Ed-monds-Gallai Theorem. Discrete Applied Mathematics, 16, 51-58. https://doi.org/10.1016/0166-218X(87)90053-9
[7]	Berge, C. (1958) Sur le couplage maximum d’un graphe. Comptes Rendus de l'Académie des Sciences (Paris) 247, 258-259.
[8]	Liu, R.F., Lai, H.J., Guo, T.L. and Xue, J. (2020) Fractional Matching Number and Spectral Radius of Nonnegative Matrix of Graphs. Linear and Multilinear Algebra, Article ID: 1865252. https://doi.org/10.1080/03081087.2020.1865252
[9]	Godsil, C. and Royle, G. (2001) Algebraic Graph Theory. In: Vakil, R., Ed., Graduate Texts in Mathematics (Vol. 207), Springer-Verlag, New York. https://doi.org/10.1007/978-1-4613-0163-9
[10]	You, L., Yang, M., So, W. and Xi, W. (2019) On the Spectrum of an Equitable Matrix and Its Application. Linear Algebra and Its Applications, 577, 21-40. https://doi.org/10.1016/j.laa.2019.04.013
[11]	Liu, Y., Su, X.L. and Xiong, D.N. (2021) Integer k-Matchings of Graphs: k-Berge-Tutte Formula, k-Factor-Critical Graphs and k-Barriers. Discrete Applied Mathematics, 297, 120-128. https://doi.org/10.1016/j.dam.2021.03.005
[12]	Ore, O. (1963) Hamiltonian Connected Graphs. Journal de Mathématiques Pures et Appliquées, 42, 21-27.