具有给定最大度的非正则图,这些图能够达到最大的谱半径
《Journal of Combinatorial Theory, Series A》:Nonregular graphs with a given maximum degree attaining the maximum spectral radius
【字体:
大
中
小
】
时间:2026年10月22日
来源:Journal of Combinatorial Theory, Series A 1.2
编辑推荐:
摘要
设G是一个连通的非正则图,其阶为n,最大度为Δ,并且达到了最大的谱半径。刘和李(2008年)[10]提出了一个猜想,认为G的度序列为(Δ,…,Δ,δ),其中δ1/2n(nΔ?1),后来张(Zhang)[18]改进了这个结果,他指出Δ?λ1(n,Δ)>(Δ?δ)/2nDΔ,其
摘要
设G是一个连通的非正则图,其阶为n,最大度为Δ,并且达到了最大的谱半径。刘和李(2008年)[10]提出了一个猜想,认为G的度序列为(Δ,…,Δ,δ),其中δ<δ。对于δ=3和δ=4的情况,刘(2024年)[8]通过描述这类图的结构证实了这一猜想。刘还提出了一个修改后的猜想,适用于固定δ且n足够大的情况,即上述δ满足:如果δ和n都是奇数,则δ=δ?1;如果δ是奇数且n是偶数,则δ=1;如果δ是偶数,则δ=δ?2。通过应用谱图论中的传统技术以及对允许循环的加权图进行某些图操作,我们完全描述了当δ=n?2且n≥5,以及δ=n?3且n≥59时g的结构。 引言 本文中提到的图都是简单的,除非另有说明。对于一个图g,我们用v(g)表示其顶点集,用e(g)表示其边集。v(g)和e(g)的基数分别称为g的阶和大小。图g中顶点v的度dg(v)是指与v相邻的边的数量,每个循环算作两条边。当图g的上下文明确时,我们可以简单地写作d(v)来表示dg(v)。我们定义δ(g)、δ(g)和dˉ(g)分别为g的最大度、最小度和平均度。g的谱半径ρ(g)是指其邻接矩阵a(g)的谱半径,它等于g的最大特征值λ1(g)。 众所周知,连通图g的谱半径小于或等于其最大度δ(g),当且仅当g是正则图时两者相等。对于非正则图,一个有趣的长久存在的问题是确定谱半径与最大度的差距有多大。这个问题最初由斯蒂瓦诺维奇(stevanovi?)[13]在2004年进行研究。设λ1(n,δ)是所有阶为n且最大度为δ的连通非正则图中的最大谱半径。斯蒂瓦诺维奇证明了δ?λ1(n,δ)>1/2n(nΔ?1),后来张(Zhang)[18]改进了这个结果,他指出Δ?λ1(n,Δ)>(Δ?δ)/2nDΔ,其中D是G的直径。乔阿巴(Cioabǎ)、格雷戈里(Gregory)和尼基福罗夫(Nikiforov)[4]证明了Δ?λ1(n,Δ)的一个更强的下界:Δ?λ1(n,Δ)>nΔ?2mn(D(nΔ?2m)+1,其中m是G的大小。他们还猜测Δ?λ1(n,Δ)>1/(nD),这一猜想后来被乔阿巴[3]证明。刘、沈和王(Liu, Shen, Wang)[12]得出了另一个下界:Δ?λ1(n,Δ)>Δ+1/n(3n+2Δ?4),这个下界稍后被刘、黄和尤(Liu, Huang, You)[9]进一步改进。在[12]中,作者还得到了Δ?λ1(n,Δ)的一个上界,最终得出Δ?λ1(n,Δ)=Θ(Δn^2)。此外,他们还猜想对于每个固定的Δ,lim_n→∞ n^2(Δ?λ1(n,Δ))/Δ?1=π/2,这一猜想被刘[8]推翻,并修改为对于奇数Δ≥3时有lim_n→∞ n^2(Δ?λ1(n,Δ))/Δ?1=π/2^4,对于偶数Δ≥3时有lim_n→∞ n^2(Δ?λ1(n,Δ))/Δ?1=π/2^2。有关这个主题的更多相关结果,读者可以参考[1]、[2]、[6]、[15]以及其中的参考文献。
研究上述问题的另一个方向是研究极端图的度序列或确切结构。设G(n,Δ)表示所有阶为n且最大度为Δ的连通非正则图的集合,这些图达到了最大的谱半径。刘和李[10]提出了以下猜想:
**猜想1** [10] 假设3≤Δ≤n?2且G∈G(n,Δ)。那么G的度序列为(Δ,…,Δ,δ),其中δ={Δ?1,如果nΔ是奇数;Δ?2,如果nΔ是偶数。对于Δ=3和Δ=4的情况,刘[8]证实了猜想1并确定了G(n,Δ)中极端图的确切结构。刘还修改了猜想1,如下:
**猜想2** [8] 假设Δ≥3且G∈G(n,Δ)。那么对于每个固定的Δ和足够大的n,G的度序列为(Δ,…,Δ,δ),其中δ={Δ?1,如果Δ和n都是奇数;1,如果Δ是奇数且n是偶数;Δ?2,如果Δ是偶数。
在本文中,我们研究了当Δ接近n时G(n,Δ)中图的结构。为了陈述我们的主要结果,我们引入以下符号。
如果存在一个双射?:V(G)→V(H),使得对于所有u,v∈V(G),uv∈E(G)当且仅当?(u)?(v)∈E(H),则称两个图G和H是同构的,记作G?H。
给定一个顶点集S?V(G),我们用G[S]表示由S诱导的G的子图。一个k-匹配,记作Mk,是k条边的不相交并集。图Kt?Mt/2是从完全图Kt中删除匹配Mt/2的边得到的图,其中t是偶数。
设G(n,t)是一个阶为n的图,它由顶点u、Kt?Mt/2和Kn?t?1的不相交并集构成,通过添加u和Kt?Mt/2之间的所有可能边以及Kt?Mt/2和Kn?t?1之间的所有可能边来构造。
设H1(n)是一个阶为n的图,其顶点集可以划分为V={u,v}∪V1∪V2,满足以下条件:
- uv∈E(H1(n)),
- H1(n)[V1]=Kn?4?M(n?4)/2,
- H1(n)[V2]=K2,
- V1中的每个顶点都与v相邻,
- V2中的每个顶点都与V1中的所有顶点相邻。
设H2(n)是一个阶为n的图,其顶点集可以划分为V={u,v1,v2}∪V1∪V2∪V3,其中|V1|=|V2|=2,并且满足以下条件:
- H2(n)[{u,v1,v2}]=K3,
- H2(n)[V1∪V2]=K4,
- H2(n)[V3]=Kn?7?M(n?7)/2,
- V3中的每个顶点都与{v1,v2}∪V1∪V2中的所有顶点相邻,
- v1与V1中的两个顶点相邻,
- v2与V2中的两个顶点相邻。参见图1,了解上述图G(n,t)、H1(n)和H2(n)。
我们的主要结果如下:
**定理3** 设n≥5是一个整数。那么G∈G(n,n?2)当且仅当G?{G(n,n?3),如果n是奇数;G∈G(n,n?4)或G∈G(n,2),如果n是偶数。
**定理4** 设n≥59是一个整数。那么G∈G(n,n?3)当且仅当当n是偶数时G?H1(n),当n是奇数时G?H2(n)。
定理4表明,对于Δ=n?3的情况,阶为n且最大度为Δ的连通图,达到最大谱半径的唯一图具有度序列(Δ,…,Δ,δ),其中δ尽可能小。这表明对于密集图来说,结构在决定谱半径方面起着比图的大小更重要的作用。
我们在第2节中给出了一些预备知识,并在第3节和第4节中展示了证明。我们的论证涉及谱图论中的传统技术,以及一些新方法,例如在允许循环的加权图上构造某些图操作。
**部分摘录**
**预备知识**
在本节中,我们介绍了一些将在整篇论文中使用的符号和预备定理。
给定一个图G=(V,E),设S?V。我们用G?S表示由S诱导的子图G[V?S],当S={v}是单个顶点时也写作G?v。S的邻域,记作N(S),是与S中的某些顶点相邻的顶点集,而S的闭邻域N[S]:=N(S)∪S。我们用G?表示G的补图,用Gloop表示通过在G的每个顶点上添加一个循环得到的图。
**定理3的证明**
假设G∈G(n,n?2)且V(G)=[n]。设X=(x1,x2,…,xn)T是G的Perron向量,其中xn对应于V(G)中的顶点k。由于G是非正则图,我们有|S|≥1。假设|S|≥2。设u,v∈S是不同的顶点,且xu=max_i∈S^2 xi。由于对于所有w∈T,d(w)=Δ=n?2,w必须与u,v中的至少一个相邻。由于xu≥xv,应用引理6我们得到NT(u)?NT(v),这意味着对于所有w∈T,w∈N(u)。因此,我们有dT(u)=|T|。另一方面,根据引理5我们有dS(u)=|S|?1。因此,d(u)=dT(u)+dS(u)=|T|+|S|?1=n?…
**定理4的证明**
假设G∈G(n,n?3)。我们断言|S|∈{1,2}。设α=(α1,α2,…,αn)T是G的Perron向量,其中αk对应于V(G)中的顶点k。由于G是非正则图,我们有|S|≥1。假设S有三个不同的顶点u1,u2,u3,且αu1=max_i∈S。由于对于所有w∈T,d(w)=Δ=n?3,w必须与u1,u2,u3中的至少一个相邻。根据引理6,我们可以推断出对于所有w∈T,w∈NT(u1),这意味着dT(u1)=|T|。另一方面,引理5表明dS(u1)=|S|?1。因此,我们有d(u1)=dT(u1)+dS(u1)=|T|+|S|?1。
**致谢**
本工作得到了中国国家自然科学基金(编号12171323)和广东省基础与应用基础研究基金(编号2022A1515011995)的支持。作者感谢薛杰教授(Jie Xue)提供的宝贵建议。
黄泽军(Zejun Huang)|刘家辉(Jiahui Liu)|杨晨曦(Chenxi Yang)δ。对于δ=3和δ=4的情况,刘(2024年)[8]通过描述这类图的结构证实了这一猜想。刘还提出了一个修改后的猜想,适用于固定δ且n足够大的情况,即上述δ满足:如果δ和n都是奇数,则δ=δ?1;如果δ是奇数且n是偶数,则δ=1;如果δ是偶数,则δ=δ?2。通过应用谱图论中的传统技术以及对允许循环的加权图进行某些图操作,我们完全描述了当δ=n?2且n≥5,以及δ=n?3且n≥59时g的结构。>