图的特征值线性组合的极值问题
《Linear Algebra and its Applications》:Extremal Problems on Linear Combinations of Graph Eigenvalues
【字体:
大
中
小
】
时间:2026年09月25日
来源:Linear Algebra and its Applications 1.1
编辑推荐:
摘要 我们研究图的关联矩阵特征值线性组合的极值问题,重点关注涉及谱半径和代数连通度的量。对于0≤α<1,定义Aα(G)=αD(G)+(1?α)A(G),并记λ1(α)(G)和a(G)分别为G的最大特征值和代数连通度。我们证明,对任意固定的0≤α<1和00和固定实数αi,βi,
摘要 我们研究图的关联矩阵特征值线性组合的极值问题,重点关注涉及谱半径和代数连通度的量。对于0≤α<1,定义Aα(G)=αD(G)+(1?α)A(G),并记λ1(α)(G)和a(G)分别为G的最大特征值和代数连通度。我们证明,对任意固定的0≤α<1和0<β≤1,在所有阶数n足够大的连通图中,λ1(α)(g)?βa(g)被风筝图kin,n?1唯一最大化。此处,风筝图kin,n?1是在n?1阶完全图的一个顶点上附加一个悬挂顶点所得的图。这一结果证实了aouchiche关于λ1(g)?a(g)的猜想,以及hansen和lucas关于q1(g)?a(g)的上界猜想的上界部分;同时也恢复了涉及点连通度、边连通度和最小度的相应极值结果。我们进一步证明,对任意阶数n≥3×2^17的连通图g,q1(g)?a(g)≥2+2cos(2π n),等号成立当且仅当g同构于圈cn。这证实了hansen–lucas猜想下界部分对充分大的n成立。 引言 谱图理论研究图的结构性质如何反映在其自然关联矩阵的特征值中。全文中所有图均为有限、简单无向图。设g为阶数n、顶点集v(g)={v1,…,vn}的图。G的邻接矩阵为A(G)=[aij],其中当vi与vj相邻时aij=1,否则aij=0。记A(G)的特征值为λ1(G)≥λ2(G)≥?≥λn(G)。我们还将使用另一个矩阵——Laplacian矩阵L(G),定义为D(G)?A(G),其中D(G)是对角矩阵,其对角元为G的顶点度。此外,矩阵Q(G):=D(G)+A(G)称为G的符号Laplacian矩阵。我们分别用μ1(G)≥μ2(G)≥?≥μn(G)和q1(G)≥q2(G)≥?≥qn(G)表示L(G)和Q(G)的特征值。特别地,L(G)的次小特征值μ2(G)通常称为G的代数连通度,记为a(G)。 谱极值图理论的核心主题之一是在结构限制下确定哪些图使给定的谱量取最大值或最小值。受邻接谱半径研究的启发,nikiforov [16]开启了图特征值线性组合极值问题的系统研究。具体地,对固定的k>0和固定实数αi,βi,γi,δi(i=1,…,k),他考虑如下形式的量:
F(G):=∑_{i=1}^{k}(αiλi(G)+βiλ_{n?i+1}(G)+γiλi(?)+δiλ_{n?i+1}(?)),
其中?是G的补图。他证明了极限lim_{n→∞}(1/n)max{F(G):|V(G)|=n}总是存在的,且对若干受限图类(如K_r-自由图)该极限同样存在。由于式(1.1)中的系数可正可负,相应的渐近极小化问题也存在极限。
本文研究涉及邻接矩阵、Laplacian矩阵和符号Laplacian矩阵特征值的极值问题。一个有用的统一对象是Nikiforov [17]引入的Aα-矩阵,定义为Aα(G):=αD(G)+(1?α)A(G),其中0≤α≤1。该矩阵在若干熟知的图矩阵之间进行插值:A0(G)=A(G),A1(G)=D(G),且2A_{1/2}(G)=Q(G)。我们记Aα(G)的最大和最小特征值分别为λ1(α)(G)和λn(α)(G)。因此λ1(0)(G)=λ1(G),而2λ1(1/2)(G)=q1(G)。
以下猜想涉及图的最大邻接特征值与代数连通度之差,最初出现在文献[1]中(另见[3])。设Kin,n?1为在n?1阶完全图的一个顶点上附加一个悬挂顶点所得的图。
猜想1.1 [1, A. 585] 设G为n阶连通图,则
λ1(G)?a(G)≤n?3+t,
其中0<β≤1。在所有n阶连通图中,当n充分大时,λ1(α)(g)?β·a(g)仅由kin,n?1最大化。 das>β≤1。在所有n阶连通图中,当n充分大时,λ1(α)(g)?β·a(g)仅由kin,n?1最大化。>
推论1.4 [13] 设g为n阶连通图,当n充分大时,
q1(g)?s≤n?(5/2)+√((4n^2?20n+33)/2),
其中s∈{κ(g),κ′(g),δ(g)},等号成立当且仅当g?kin,n?1。
我们的第二个结果表明,猜想1.2的下界对所有阶数充分大的连通图成立。
定理1.2 设g为n阶连通图,若n≥3×2^17,则
q1(g)?a(g)≥2+2cos(2π/n),
等号成立当且仅当g?cn。
本文其余部分组织如下。第2节收集aα-矩阵、rayleigh商和代数连通度的预备知识。第3节证明定理1.1。最后一节证明定理1.2。
对子集x?v(g),记g[x]为x诱导的子图,g?x为从g中删除x中所有顶点所得的图。对不相交或不交集子集x,y?v(g),e(x,y)表示一端点在x、另一端点在y的边的集合,e(x)表示x诱导的边的集合。对顶点v∈v(g),记dg(v)和ng(v)分别为其在g中的度和邻域;当图由上下文可知时,简记为d(v)和n(v)。g的最大度和最小度分别记为δ(g)和δ(g)。按惯例,kn、k1,n?1、pn和cn分别表示n阶完全图、星形、路和圈。对于本文未定义的图论术语,请参阅[4]。
节摘要
预备知识 本节回顾特征值-特征向量方程、矩阵二次型以及全文将使用的一些必要结论。
定理1.1的证明 本节将给出定理1.1的证明。在此之前,我们列出一些辅助结果。
命题3.1 [10] 下列命题成立:
(1) a(k_{p,q})=min{p,q}。
(2) 若h是g的生成子图,则a(h)≤a(g)。
命题3.2 [10] 设g为非完全图,则a(g)≤δ(g)。
以下断言是命题3.1和命题3.2的简单推论。
命题3.3 a(kin,n?1)=1。
证明 由命题3.2,a(kin,n?1)≤δ(kin,n?1)=1。另一方面,由于k1,n?1是kin,n?1的生成子图,由命题3.1可得a(kin,n?1)≥a(...)(原文此处截断)
定理1.2的证明 本节旨在证明定理1.2,从而确认猜想1.2的下界。
huan wang | lele liu 推论1.4 [13] 设g为n阶连通图,当n充分大时, q1(g)?s≤n?(5 2)+√((4n^2?20n+33) 2), 其中s∈{κ(g),κ′(g),δ(g)},等号成立当且仅当g?kin,n?1。 我们的第二个结果表明,猜想1.2的下界对所有阶数充分大的连通图成立。 定理1.2 设g为n阶连通图,若n≥3×2^17,则 q1(g)?a(g)≥2+2cos(2π n), 等号成立当且仅当g?cn。 本文其余部分组织如下。第2节收集aα-矩阵、rayleigh商和代数连通度的预备知识。第3节证明定理1.1。最后一节证明定理1.2。 对子集x?v(g),记g[x]为x诱导的子图,g?x为从g中删除x中所有顶点所得的图。对不相交或不交集子集x,y?v(g),e(x,y)表示一端点在x、另一端点在y的边的集合,e(x)表示x诱导的边的集合。对顶点v∈v(g),记dg(v)和ng(v)分别为其在g中的度和邻域;当图由上下文可知时,简记为d(v)和n(v)。g的最大度和最小度分别记为δ(g)和δ(g)。按惯例,kn、k1,n?1、pn和cn分别表示n阶完全图、星形、路和圈。对于本文未定义的图论术语,请参阅[4]。 节摘要 预备知识 本节回顾特征值-特征向量方程、矩阵二次型以及全文将使用的一些必要结论。 定理1.1的证明 本节将给出定理1.1的证明。在此之前,我们列出一些辅助结果。 命题3.1 [10] 下列命题成立: (1) a(k_{p,q})=min{p,q}。 (2) 若h是g的生成子图,则a(h)≤a(g)。 命题3.2 [10] 设g为非完全图,则a(g)≤δ(g)。 以下断言是命题3.1和命题3.2的简单推论。 命题3.3 a(kin,n?1)=1。 证明 由命题3.2,a(kin,n?1)≤δ(kin,n?1)=1。另一方面,由于K1,n?1是Kin,n?1的生成子图,由命题3.1可得a(Kin,n?1)≥a(...)(原文此处截断) 定理1.2的证明 本节旨在证明定理1.2,从而确认猜想1.2的下界。 huan wang | lele>
推论1.4 [13] 设g为n阶连通图,当n充分大时,
q1(g)?s≤n?(5/2)+√((4n^2?20n+33)/2),
其中s∈{κ(g),κ′(g),δ(g)},等号成立当且仅当g?kin,n?1。
我们的第二个结果表明,猜想1.2的下界对所有阶数充分大的连通图成立。
定理1.2 设g为n阶连通图,若n≥3×2^17,则
q1(g)?a(g)≥2+2cos(2π/n),
等号成立当且仅当g?cn。
本文其余部分组织如下。第2节收集aα-矩阵、rayleigh商和代数连通度的预备知识。第3节证明定理1.1。最后一节证明定理1.2。
对子集x?v(g),记g[x]为x诱导的子图,g?x为从g中删除x中所有顶点所得的图。对不相交或不交集子集x,y?v(g),e(x,y)表示一端点在x、另一端点在y的边的集合,e(x)表示x诱导的边的集合。对顶点v∈v(g),记dg(v)和ng(v)分别为其在g中的度和邻域;当图由上下文可知时,简记为d(v)和n(v)。g的最大度和最小度分别记为δ(g)和δ(g)。按惯例,kn、k1,n?1、pn和cn分别表示n阶完全图、星形、路和圈。对于本文未定义的图论术语,请参阅[4]。
节摘要
预备知识 本节回顾特征值-特征向量方程、矩阵二次型以及全文将使用的一些必要结论。
定理1.1的证明 本节将给出定理1.1的证明。在此之前,我们列出一些辅助结果。
命题3.1 [10] 下列命题成立:
(1) a(k_{p,q})=min{p,q}。
(2) 若h是g的生成子图,则a(h)≤a(g)。
命题3.2 [10] 设g为非完全图,则a(g)≤δ(g)。
以下断言是命题3.1和命题3.2的简单推论。
命题3.3 a(kin,n?1)=1。
证明 由命题3.2,a(kin,n?1)≤δ(kin,n?1)=1。另一方面,由于k1,n?1是kin,n?1的生成子图,由命题3.1可得a(kin,n?1)≥a(...)(原文此处截断)
定理1.2的证明 本节旨在证明定理1.2,从而确认猜想1.2的下界。
huan wang | lele liu>β≤1,在所有阶数n足够大的连通图中,λ1(α)(g)?βa(g)被风筝图kin,n?1唯一最大化。此处,风筝图kin,n?1是在n?1阶完全图的一个顶点上附加一个悬挂顶点所得的图。这一结果证实了aouchiche关于λ1(g)?a(g)的猜想,以及hansen和lucas关于q1(g)?a(g)的上界猜想的上界部分;同时也恢复了涉及点连通度、边连通度和最小度的相应极值结果。我们进一步证明,对任意阶数n≥3×2^17的连通图g,q1(g)?a(g)≥2+2cos(2π>