两类极小图的谱半径与极值图
《Discrete Mathematics》:The spectral radii and extremal graphs of two types of minimal graphs
【字体:
大
中
小
】
时间:2026年10月23日
来源:Discrete Mathematics 1.1
编辑推荐:
摘要 一个连通且非平凡的图$G$被称为匹配覆盖图,如果$G$的每一条边都包含在$G$的某个完美匹配中。如果对于$G$的每一条边$e$,$G-e$都不是匹配覆盖图,则称匹配覆盖图$G$是最小的。若对于$V(G)$中的每个顶点$v$,$G-v$都有完美匹配,则称图$G$是因子临界
摘要 一个连通且非平凡的图$G$被称为匹配覆盖图,如果$G$的每一条边都包含在$G$的某个完美匹配中。如果对于$G$的每一条边$e$,$G-e$都不是匹配覆盖图,则称匹配覆盖图$G$是最小的。若对于$V(G)$中的每个顶点$v$,$G-v$都有完美匹配,则称图$G$是因子临界的。若对于$E(G)$中的每条边$e$,$G-e$都不是因子临界的,则称因子临界图$G$是最小因子临界的。本文利用耳分解和边交换技术,确定了最小匹配覆盖二部图和最小因子临界图的最大谱半径,并刻画了相应的极值图。
引言 本文中讨论的图都是连通的简单图。关于标准图论符号和术语,请参考文献[3]、[16]。设$G$是一个具有顶点集$V(G)$和边集$E(G)$的图。$G$的阶记为$n$,即$n=|V(G)|$。我们用$K_n$表示$n$阶完全图。$G$的补图$\overline{G}$是指顶点集为$V(G)$,边集为$G$中所有不相邻顶点对构成的简单图。图$G$和$H$的并是顶点集为$V(G)\cup V(H)$、边集为$E(G)\cup E(H)$的图$G\cup H$。如果$G$和$H$是边不交的,则$G\cup H$可记为$G+H$。图$G\vee H$是由不相交的图$G$和$H$的并得到的图,其中添加了$G$的顶点与$H$的顶点之间的所有边。我们用$P_n$和$C_n$分别表示$n$阶路径和$n$阶圈。若图的顶点集可以划分为两个子集$X$和$Y$,使得每条边都有一个端点在$X$中,另一个端点在$Y$中,则称该图为二部图;这样的划分$(X,Y)$称为图的二部划分,$X$和$Y$为其部集。
$G$的一个匹配是一组两两不相邻的边的集合。$G$的一个完美匹配是覆盖$G$所有顶点的匹配。一个连通非平凡图$G$是匹配覆盖的,如果$G$的每一条边都包含在$G$的某个完美匹配中。如果对于$G$的每一条边$e$,$G-e$都不是匹配覆盖的,则称匹配覆盖图$G$是最小的。Lovász和Plummer [15]给出了最小匹配覆盖二部图的边数的上界,并刻画了极值图。Zhang等人[25]给出了无爪的最小匹配覆盖图的完整刻画。He等人[9]证明了除$K_2$外的最小匹配覆盖图的最小度为2或3。Mallik等人[17]刻画了其中2度顶点数为$2(m-n+2)$的最小匹配覆盖二部图,其中$m=|E(G)|$,$n=|V(G)|$。
若对于$V(G)$中的每个顶点$v$,$G-v$都有完美匹配,则称图$G$是因子临界的。若对于$E(G)$中的每条边$e$,$G-e$都不是因子临界的,则称因子临界图$G$是最小的。Favaron [5]和Yu [20]独立地引入了$k$-因子临界图。对于整数$k$,其中$1\le k\le n-2$且$n\equiv k\pmod{2}$,若对于所有满足$|S|=k$的子集$S\subseteq V(G)$,$G-S$都有完美匹配,则称$n$阶图$G$是$k$-因子临界的。Zhang和Fan [23]分别建立了保证$G$是$k$-因子临界的边数下界和谱半径下界。
设$A(G)$为图$G$的邻接矩阵。$A(G)$的最大特征值称为$G$的谱半径,记为$\rho(G)$。由Perron-Frobenius定理[10],$n$阶连通图$G$对应于$\rho(G)$有一个正的单位特征向量$x=(x_1,x_2,\ldots,x_n)^T$,称为$G$的Perron向量。
谱图理论中最著名的一个问题之一是以下Brualdi-Solheid问题[4]。
问题1 Brualdi-Solheid问题
给定一个图集合$\mathcal{G}$,求$\mathcal{G}$中图的谱半径的紧上界,并刻画极值图。
该问题在文献中已被广泛研究,涉及许多类的图,如具有割点的图[2]、具有割边的图[12]、给定色数的图[6]、给定直径的图[8]、给定支配数的图[19]、给定独立数的图[11]、[13]。Feng等人[7]刻画了$n$阶匹配数为$\beta$的简单图中具有最大谱半径的极值图。Zhang等人[22]、[24]分别在匹配数至多为$\frac{n-k}{2}$的$t$-连通图中和在最小度为$\delta$且匹配数至多为$\frac{n-k}{2}$的连通图中刻画了这些图,其中$t$、$k$为正整数。在本文中,我们利用耳分解和边交换技术,确定了最小匹配覆盖二部图和最小因子临界图的最大谱半径,并刻画了极值图。主要结果如下。
定理1.1 设$G$是$n$阶最小匹配覆盖二部图。若$n\le 4$,则$\rho(G)\le 2$,等号成立当且仅当$G\cong C_4$。若$n\ge 6$,则$\rho(G)\le 1+\sqrt{\frac{2(n-3)}{2}}$,等号成立当且仅当$G\cong P_3^*$,其中$P_3^*$是$\frac{n-2}{2}$条具有相同端点的长度为3的路径的并(见图1)。
定理1.2 设$G$是$n$阶最小因子临界图。则$\rho(G)\le \rho(K_1\vee \frac{n-1}{2}K_2)$,等号成立当且仅当$G\cong K_1\vee \frac{n-1}{2}K_2$。
预备知识
我们从本文中所使用的一些定义和符号开始。对于$V(G)$的任意子集$S$,令$N_G(S)$表示$V(G)\setminus S$中所有与$S$中至少一个顶点相邻的顶点的集合。我们用$G-S$表示从$G$中删除$S$中的顶点及其关联边所得的子图,用$G[S]$表示$G$中由$S$导出的子图。对于$E(G)$的子集$E'$,$G-E'$表示从$G$中删除$E'$中的边所得的图。类似地,$G+E'$表示从$G$中……
最小匹配覆盖二部图
在本节中,我们给出了最小匹配覆盖二部图谱半径的上界,并刻画了极值图。设$G$是具有二部耳分解$C+P_1+P_2+\cdots+P_k$的最小匹配覆盖二部图。我们定义该耳分解中各耳的级数。耳$C$称为0级耳。耳$P_1$称为1级耳。对于耳$P_i$($i\ge 2$),若$P_i$的一个端点是$k$级耳的内部顶点,另一个端点是$l$级耳的内部顶点,则……
最小因子临界图
在本节中,我们利用因子临界图的耳分解来确定最小因子临界图谱半径的紧上界,并刻画极值图。首先,我们介绍一些定义和引理,为后续证明奠定基础。
定义4.1 若$B$是图$G$的一个极大连通子图且没有割点,则称$B$为$G$的一个块。特别地,若$B$只包含$G$的一个割点,则称$B$为$G$的端块。
致谢
本文作者受国家自然科学基金(12571381和12371361)、河南青年人才支持项目(2026HYTP025)和河南省自然科学基金(252300420303和262300421874)资助。牛孟元的研究受国家留学基金委(编号202507040066)资助。
连立文 | 刘金峰 | 牛孟元 | 王秀梅
生物通微信公众号
生物通新浪微博
今日动态 |
人才市场 |
新技术专栏 |
中国科学人 |
云展台 |
BioHot |
云讲堂直播 |
会展中心 |
特价专栏 |
技术快讯 |
免费试用
版权所有 生物通
Copyright© eBiotrade.com, All Rights Reserved
联系信箱:
粤ICP备09063491号