贵州大学，数学与统计学院，贵州 贵阳

收稿日期：2022年12月10日；录用日期：2023年1月11日；发布日期：2023年1月20日

摘要

令G表示为图，图G的k-匹配是一个函数f，它为G的每个边分配 $\left\{0,1,\cdots ,k\right\}$ 中的一个数，使得G的每个顶点v均有 ${\displaystyle {\sum }_{e~v}f\left(e\right)}\le k$，这里的求和表示取遍所有与定点邻接的边e。在本文中，我们探讨了当k为奇数时，图的 $A_{\alpha }$ -谱半径与整数k-匹配数之间的关系。

关键词

k-匹配理论，谱半径，商矩阵

The $A_{\alpha }$ -Spectral Radius and k-Matching Number in Graphs

Zhen Li, Chao Zhang^*

Department of Mathematics, Guizhou University, Guiyang Guizhou

Received: Dec. 10^th, 2022; accepted: Jan. 11^th, 2023; published: Jan. 20^th, 2023

ABSTRACT

Let G be a graph. A k-matching of G is a function f that assigns to each edge of G a number in $\left\{0,1,\cdots ,k\right\}$ so that ${\displaystyle {\sum }_{e~v}f\left(e\right)}\le k$ for each vertex v of G, where the sum is taken over all edges e incident with v. In our paper, we explore the relationship between $A_{\alpha }$ -spectral radius and integer k-matching number in general graphs when k is odd.

Keywords:k-Matching Theory, Spectral Radius, Quotient Matrix

Copyright © 2023 by author(s) and Hans Publishers Inc.

This work is licensed under the Creative Commons Attribution International License (CC BY 4.0).

http://creativecommons.org/licenses/by/4.0/

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)资助。

文章引用

李 振,章 超. 图的A_α-谱半径与k-匹配数
The A_α-Spectral Radius and k-Matching Number in Graphs[J]. 理论数学, 2023, 13(01): 67-73. https://doi.org/10.12677/PM.2023.131007

参考文献