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

来源:用户上传      作者:李梦霞 耿显亚

　　摘 要：对于任意的[α∈0，1]，Nikiforov提出了矩阵[AαG=αDG+1-αAG]，记为图[G]的[Aα]-矩阵，其中[AG]是[G]的邻接矩阵，[DG]是[G]的度对角矩阵.矩阵[AαG]的最大特征值称为图[G]的[Aα]-谱半径.本文考虑有[k]个悬挂点的所有单圈图，确定了具有最大[Aα]-谱半径的图.
　　关键词：单圈图；[Aα]-谱半径；最大特征值；悬挂点
　　[ 中图分类号 ]O157.5 [ 文献标志码 ] A
　　
　　On the [Aα]-spectral Radius of Unicyclic Graphs with [k]
　　Pendant Vertices
　　LI Mengxia，GENG Xianya
　　（School of Mathematics and Big Data，Anhui University of Science & Technology，Huainan 232000，China）
　　Abstract：For any real[α∈0，1]，Nikiforov proposed the matrix[AαG=αDG+1-αAG]，which is the [Aα]-matrix of a graph [G]，where [AG] is the adjacency matrix of [G] and [DG] is the diagonal matrix of the degrees of [G]. In this paper，we determine the graph with the largest[Aα]-spectral radius among all unicyclic graphs with [k] pendant vertices.
　　Key words：unicyclic graph；[Aα]-spectral radius；largest eigenvalue；pendant vertice
　　当前，图的[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]条边组成.设[AG]，[DG]分别是图[G]的邻接矩阵和度对角矩阵.图[G]的无符号拉普拉斯矩阵被定义为[QG=DG+AG].对于任意的[α∈0，1]，Nikiforov[11]提出了矩阵[AαG=αDG+1-αAG].容易看出，[A0G=AG]，并且[A12G=2QG]，因此[A12G]就等价于无符号拉普拉斯矩阵[QG].用[ραG]表示矩阵[AαG]的最大特征值，即图[G]的[Aα]-谱半径.在图[G]中，与点[v]相邻的点的集合称为点[v]的邻域，记作[NGv]（在没有歧义的情况下，下标可以省略）.与点[v]相关联的边的个数称为点[v]的度，记作[dGv].显然，[dGv=NGv].[Γn，k]表示有[n]个顶点和[k]个悬挂点的所有树集，树[Tn，k]是通过在星图[K1，k]上添加[k]条长度不超过2的悬挂边得到的.用[Cn]，[Pn]分别定义有[n]的点的圈和路.边数等于点数的连通图称为单圈图.显然一个单圈图要么是一个独立的圈，要么是由圈和c圈相连的树构成.用[Unk]定义有[n]个顶点和[k]个悬挂点的所有单圈图集，用[Δkn]表示在圈[C3]上添加[k]条长度不超过2的悬挂边，使该单圈图有[n]个顶点和[k]个悬挂点.本文考虑有[k]个悬挂点的所有单圈图，确定了具有最大[Aα]-谱半径的图.
　　1 主要引理
　　引理1 设[u，v]是连通图[G]上的两个顶点，[N?Vv＼Nu?u] ，且[x]是[ραG]的对应单位特征向量.假设[G=G-vω：ω∈N+uω：ω∈N]，如果[N≠?]且[xu>xv]，那么，[ραG<ραG]，[mG=mG].[2，3]
　　引理2 设[u]是连通图[G]上的一个顶点且[du≥2]，新图[Gp，qu]是通过在点[u]上连接两条长为[p]和[q]的路得到的.假设[α∈0，1]，如果[p-q≥2]，则[ραGp，qu≤ραGp-1，q+1u].[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]

nlc202211251451

　　情况2：[t=1].根据引理2，容易证明[T=Tn，k]时等式成立.
　　情况3：[t>1].假设[X=x1x2…xn]是树[T]的单位特征向量，其中[xi]对应[vi1≤i≤n].设[u，v]是[T]上度数大于等于3的两个顶点，且[xu≥xv].由于在点[u，v]间有一条路，所以设在该路上与[v]相邻的点为[ω].假设[V1=v1v2…vdv-2 ?NGv＼ω]，[T′1=T-vvivi∈V1+uvivi∈V1]，显然，[T′1]仍然有[k]个悬挂点.根据引理1，得到[ραT≤ραT′1]并且度数大于等于3的顶点个数变为[t-1].
　　如果[t-1>1]，将树[T′1]重复做以上变形，直到个数变为1，从而得到树[T'2，T'3…T't-1].根据引理1得到[ραT'2<ραT'3<…<ραT't-1].根据情况2 ，得到[ραT't-1≤ραTn，k]，因此，[ραT<ραTn，k].证明结束.
　　定理2 假设[G]是有[n]个顶点和[k]个悬挂点的单圈图，如果[α∈0，1]，那么，[ραG≤ραΔkn]，当且仅当[G=Δkn]时等式成立.（见图1）
　　证明 设[G∈Unk]，[V（G）=v1v2…vn]，对应单位特征向量[X=x1x2…xn]，其中[xi]对应[vi1≤i≤n].
　　第一步，证明图[G]上只有顶点[v1]上附着树[T].假设存在点[vi]上附着一个树[v1≠vi]，[vi]是圈[Cp]上的点.设[Nvi=vi-1，vi+1，z1…zs]，[Nv1=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∈Unk]，根据引理1，得到[ραG<ραG]，矛盾.因此，图[G]只有一个附着树.
　　第二步，证明树[T]上所有顶点的度都不超过2.假设[vi]是[T]上的一点且[dvi>2].令[Nvi=z1…zt]，[Nv1=ω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∈Unk]，根据引理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∈Unk].通过引理3，得到 [ραG<ραG]，矛盾.因此，[p=3].
　　通过上述证明，得到当[G=Δkn]时，单圈图具有最大[Aα]-谱半径.证明结束.
　　3 总 结
　　本文证明了当[T=Tn，k]时，树具有最大[Aα]-谱半径，分析了有[k]个悬挂点的所有单圈图，确定了具有最大[Aα]-谱半径的图.这为接下来关于[Aα]-谱半径的更多研究提供了思路.
　　参考文献
　　[1]V Nikiforov，G Pasten，O Rojo，R.L. Soto. On the[Aα]-spectra of trees [J]. Linear Algebra Appl，2017，520： 286-305.
　　[2]J Xue，HQ Lin，ST Liu，JL Shu. On the[Aα]-spectral radius of a graph [J]. Linear Algebra Appl，2018，550： 105-120.
　　[3]V Nikiforov，O Rojo. On the[Aα]-index of graphs with pendent paths [J]. Linear Algebra Appl，2018，55： 87-104.
　　[4]HQ Lin，J Xue，JL Shu. On the[Aα]-spectra of graphs [J]. Linear Algebra Appl. 2018，556： 210-219.
　　[5]HQ Lin，XG Liu，J Xue. Graphs determined by their[Aα]-spectra [J]. Discret. Math. 2019，342： 441-450.
　　[6]荣，郭曙光. 单圈图与双圈图补图的[Aα]-谱半径[J]. 高校应用数学学报. 2021，36（2）： 247-252.
　　[7]凤宝林. 一个可修复的[m，N]系统实特征值的存在性[J]. 牡丹江师范学院学报： 自然科学版，2008（4）：1-2.
　　[8]徐礼礼，董晓媛，马登举. 一个路与一个完全二部图直积的[L2，1]-标[J]. 牡丹江师范学院学报： 自然科学版，2016（2）： 7-8.
　　[9]Shu-Guang Guo. The spectral radius of unicyclic and bicyclic graphs with [n]vertices and[k]pendant vertices [J]. Linear Algebra and its Applications，2005，408： 78-85.
　　[10]B.F. Wu，E.L. Xiao，and Y. Hong.The spectral radius of trees on[k]pendant vertices [J]. Linear Algebra Appl，2005，395： 343-349.
　　[11]V Nikiforov. Merging the [A]- and [Q]-spectral theories [J]. Appl. Anal. Discrete Math，2017，11： 81-107.
　　[12]Dan Li，Yuanyuan Chen，Jixiang Meng. The[Aα]-spectral radius of trees and unicyclic graphs with given degree sequence [J]. Applied Mathematics and Computation，2019，363：124622.
　　编辑：琳莉

nlc202211251451

转载注明来源:https://www.xzbu.com/1/view-15442556.htm