具有k个悬挂点的单圈图的Aα-谱半径

李梦霞，耿显亚

（安徽理工大学 数学与大数据学院，安徽 淮南 232001）

当前，图的Aα-矩阵引起了学者的广泛关注，成为研究的热点.Nikiforov［1］等刻画了在所有n阶连通图中，Aα-谱半径最小的图.Xue［2］等刻画了在Aα-谱半径上的三种边变换方法.作为应用，Nikiforov［3］等和Xue等独立确定了给定直径的图中Aα-谱半径最大的图和给定团数的图中Aα-谱半径最小的图.Lin［4］等给出了有关Aα(G)矩阵特征值的一些性质.关于一个图能否由其Aα-谱半径确定的研究才刚刚开始.Lin［5］等证明了在一定条件下，有一些图可以由其Aα-谱半径确定.关于Aα-谱半径的更多成果参考文献［6-8］.Guo［9］等刻画了有k个悬挂点的所有单圈图和双圈图中谱半径最大的图，Wu［10］等确定了有k个悬挂点的树中谱半径最大的图.

本文考虑的是有限无向简单图.G=(V，E)是由n= |V|个顶点和m= |E|条边组成.设A(G)，D(G)分别是图G的邻接矩阵和度对角矩阵.图G的无符号拉普拉斯矩阵被定义为Q(G)=D(G)+A(G).对于任意的α∈[0，1]，Nikiforov［11］提出了矩阵Aα(G)=αD(G)+(1-α)A(G).容易看出，A0(G)=A(G)，并且(G)=2Q(G)，因此(G)就等价于无符号拉普拉斯矩阵Q(G).用ρα(G)表示矩阵Aα(G)的最大特征值，即图G的Aα-谱半径.在图G中，与点v相邻的点的集合称为点v的邻域，记作NG(v)（在没有歧义的情况下，下标可以省略）.与点v相关联的边的个数称为点v的度，记作dG(v).显然，dG(v)= |NG(v)|.Γn，k表示有n个顶点和k个悬挂点的所有树集，树Tn，k是通过在星图K1，k上添加k条长度不超过2的悬挂边得到的.用Cn，Pn分别定义有n的点的圈和路.边数等于点数的连通图称为单圈图.显然一个单圈图要么是一个独立的圈，要么是由圈和与圈相连的树构成.用Un(k)定义有n个顶点和k个悬挂点的所有单圈图集，用表示在圈C3上添加k条长度不超过2的悬挂边，使该单圈图有n个顶点和k个悬挂点.本文考虑有k个悬挂点的所有单圈图，确定了具有最大Aα-谱半径的图.

1 主要引理

引理1设u，v是连通图G上的两个顶点，N⊆V(v)(N(u)∪{u})，且x是ρα(G)的对应单位特征向量.假设G'=G-{vω：ω∈N}+{uω：ω∈N}，如果N≠∅且xu＞xv，那么，ρα(G)＜ρα(G')，m(G)=m(G').［2，3］

引理2设u是连通图G上的一个顶点且d(u)≥2，新图Gp，q(u)是通过在点u上连接两条长为p和q的路得到的.假设α∈[0，1)，如果p-q≥2，则ρα(Gp，q(u))≤ρα(Gp-1，q+1(u)).［12］

引理3设G是一个连通图，uv是图G内部路中的边.图Guv表示在边uv上添加一个点ω使uv=uω+vω，那么，ρα(Guv)＜ρα(G)，这里α∈[0，1).［12］

2 重要结论

定理1假设T是有n个顶点和k个悬挂点的树，如果α∈[0，1)，那么，ρα(T)≤ρα(Tn，k)，当且仅当T=Tn，k时等式成立.

证明假设度数大于等于3的顶点个数为t：

情况1：t=0.T是一条长为n的路，因此，T=Tn，2，则ρα(T)=ρα(Tn，2)

情况2：t=1.根据引理2，容易证明T=Tn，k时等式成立.

情况3：t＞1.假设X={x1x2…xn}是树T的单位特征向量，其中xi对应vi(1≤i≤n).设u，v是T上度数大于等于3的两个顶点，且xu≥xv.由于在点u，v间有一条路，所以设在该路上与v相邻的点为ω.假设，显然，T1'仍然有k个悬挂点.根据引理1，得到ρα(T)≤ρα(T1')并且度数大于等于3的顶点个数变为t-1.

如果t-1＞1，将树T1'重复做以上变形，直到个数变为1，从而得到树T2'，T3'…Tt'-1.根据引理1得到ρα(T2')＜ρα(T3')＜…＜ρα(Tt'-1).根据情况2，得到ρα(Tt'-1)≤ρα(Tn，k)，因此，ρα(T)＜ρα(Tn，k).证明结束.

定理2假设G是有n个顶点和k个悬挂点的单圈图，如果α∈[0，1)，那么，，当且仅当G=时等式成立.（见图1）

图1 图G与图

证明设G∈Un(k)，V(G)={v1v2…vn}，对应单位特征向量X={x1x2…xn}，其 中xi对应vi(1≤i≤n).

第一步，证明图G上只有顶点v1上附着树T.假设存在点vi上附着一个树(v1≠vi)，vi是圈Cp上的点.设N(vi)={vi-1，vi+1，z1…zs}，N(v1)={vj-1，vj+1，ω1…ωt}，其中，vi-1，vi+1，vj-1，vj+1都是圈Cp上的点.那么，s≥1，t≥2.如果x1≥xi，设G'=G-{viz1…vizs}+{v1z1…v1zs}.如果x1＜xi，设G'=G-{v1ω1…v1ωt}+{viω1…viωt}.因为G'∈Un(k)，根据引理1，得到ρα(G)＜ρα(G')，矛盾.因此，图G只有一个附着树.

第二步，证明树T上所有顶点的度都不超过2.假设vi是T上的一点且d(vi)＞2.令N(vi)={z1…zt}，N(v1)={ω1…ωs}，假 设z1，ω3是 路v1vi上 的 点且ω1∈Cp，ω2∈Cp.如果x1≥xi，设G'=G-{viz3…vizt}+{v1z3…v1zt}.

如果x1＜xi，设G'=G-{v1ω1，v1ω4…v1ωs}+{viω1，viω4…viωs}.因为G'∈Un(k)，根据引理1，得到ρα(G)＜ρα(G')，矛盾.因此，树T上所有顶点的度都不超过2.

第三步，证明附着在点v1上的k条悬挂路是几乎等长的（长度不超过2）.根据定理1很容易看出.

第四步，证明圈Cp长为3.假设p≥4.设Cp=v1v2…vpv1，显然G≠Cp，v1v2…vpv1是一条封闭的内部路.设G'=G-{v2v3，v3v4}+{v2v4}，那么，G'∈Un(k).通过引理3，得到ρα(G)＜ρα(G')，矛盾.因此，p=3.

通过上述证明，得到当G=时，单圈图具有最大Aα-谱半径.证明结束.

3 总结

本文证明了当T=Tn，k时，树具有最大Aα-谱半径，分析了有k个悬挂点的所有单圈图，确定了具有最大Aα-谱半径的图.这为接下来关于Aα-谱半径的更多研究提供了思路.