4度点数固定的树的距离谱半径
汪 云, 吴宝丰
【摘 要】摘要： 引入了一种图的变换,得到了距离谱半径的变化规律.进一步研究了四度点数固定的树集,刻画了该图类中距离谱半径最大的极图.最后,讨论了更一般的图类,即度至少为4的点数固定的树集,并确定了极图. 【期刊名称】上海理工大学学报 【年(卷),期】2017(039)005 【总页数】7
【关键词】 距离矩阵; 距离谱半径; 距离Perron向量; 树
1 基本概念
研究的图均为连通的简单无向图.设G是n阶连通图,V(G)和E(G)分别是顶点集和边集.对于任意顶点v∈V(G),用NG(v)表示它的邻集,并根据其度数的奇偶性,称它为奇度点或偶度点.对于图G的任意2点u,v,用dG(u,v)表示它们的距离,D(G)=(dG(u,v))u,v∈V(G)表示图G的距离矩阵.显然,D(G)是实对称的,所以,它的特征值全为实数.图G的距离谱半径用ρ(G)表示,代表D(G)的最大特征值.连通图对应的距离矩阵是不可约的,由Perron-Frobenius定理可知,ρ(G)是单根,且有相应的正单位特征向量,记为X(G),称为G的距离Perron向量.
任取向量X=(x1,…,xn)T∈n (这里X可能是G的距离Perron向量,也可能不是),可将它的分量与G中的点一一对应,即分量xi对应顶点vi,则 若X是D(G)的相应于λ的特征向量,则对每一点u∈V(G),有 (1)
称式(1)为G在u点处的(λ,X)-特征方程.对于任意单位向量X∈n,由Rayleigh-
Ritz定理[1],有 ρ(G)≥XTD(G)X
当X是G的距离Perron向量时,上式等号成立.对于G的子图H,记σG(H)为G的距离Perron向量中对应于V(H)的所有分量之和.
Pn表示n阶路,它是n阶连通图中距离谱半径最大的图[2].若一棵树,将其所有悬挂点删去后所得图是一条路,则称该树为毛毛虫图.显然,Pn自身也是毛毛虫图. 设V1?V(G),则G-V1表示将图G删去V1中的点以及相关联的所有边后所得到的图.若V1={u},则用G-u来代替G-{u}.对于E1?E(G),G-E1表示将图G删去E1中的边后所得到的图.相应地,用G-uv来代替G-{uv}.若E′是G的补图的一些边的集合,类似地,可以定义G+E′和G+uv.
距离矩阵的定义可以追溯到1841年Cayley 的论文[3],后来Graham[4]于1971年在距离矩阵的负特征值个数与数据通信系统中的寻址问题之间建立了一种关系,自此,距离谱的研究引起了众多图论学者的兴趣.与邻接矩阵相比,距离矩阵包含了图的更多信息,但同时也更加复杂,任意一条边的移动或者删除,都会给距离矩阵带来很大的变化,所以,研究难度较大.关于距离谱的综述见文献[5]. 文献[6]研究了奇度点数固定的树集,刻画了距离谱半径最大的极图.受此启发,本文研究4度点数固定的树集,以及度至少为4的点数固定的树集,刻画了距离谱半径最大的极图.
2 关于图C(n,a,b)
现引入一类图C(n,a,b),并得到了一些性质.在考虑4度点数固定的树集时,距离谱半径最大的图就是此类图.
定义1 设b≥a≥0,3(a+b)≤n-2,r=n-3a-3b-2,记图1所示的图为C(n,a,b).特别
地,C(n,0,0)是路Pn.
定义2 设2≤Δ≤n-1,路Pn-Δ+1的1个端点连接Δ-1个悬挂点所得到的图记为Bn,Δ,如图2所示.
引理1[7] 设T是n(n≥4)阶树,Δ为最大度,则ρ(T)≤ρ(Bn,Δ),等式成立当且仅当T?Bn,Δ.进一步,若Δ1>Δ2,则ρ(Bn,Δ1)<ρ(Bn,Δ2).
推论1 设T是n(n≥5)阶树,最大度Δ≥4,则ρ(T)≤ρ(C(n,0,1)),等式成立当且仅当T?C(n,0,1).
证明 因为,Δ≥4,由引理1可知,ρ(T)≤ρ(Bn,Δ)≤ρ(Bn,4)=ρ(C(n,0,1)),等号成立当且仅当T=C(n,0,1),证毕.
引理2[7] 设G是n阶连通图,X是G的距离Perron向量,其分量xv与顶点v对应.令u,v∈V(G),u′,v′分别是u,v的悬挂邻点,则-=(xu-xv).
引理3[6] 设T是树,u∈V(T),NT(u)={u1,…,uk},其中,k≥3,Ti为T-u的包含ui(1≤i≤k)的分支,w∈V(Tk),对于任意
t=2,3,…,k-1,令
T′=T-
{uui:2≤i≤t}+{wui:2≤i≤t}.若σT(Tk)≤σT(T1),则ρ(T′)>ρ(T).
引理4[8] 设G是n阶连通图,X=(x1,x2,…,xn)T是G的距离Perron向量,其分量xi与顶点vi对应.令vi-1vi,vivi+1是G的2条边,且vi-1vi,vivi+1中至少有1条是割边,若xi-1 引理5 设图C(n,a,b)如图1所示,b≥a+2≥2, 3(a+b) 证明 设图C(n,a,b)的直径为d,对图1进行重新编号,如图3所示,并设X的分量xi,,分别对应顶点,t=,则结论a和b转化为结论c和d. c. 0 xa+1-xa+r+1>xa+2-xa+r>…>xa+s-xa+t+1>0, 其 中 ,a+r+1=d- b,a+t+1=a+r+2-s. 现证明结论c. 令p=,q=,且对于任意i=0,1,…,d,令 断言1 xp>xq+1. 假设用数学归纳法可推出xp-i≤xq+1+i(0≤i≤p). 当i=0时,由式(1)可知, (2) 在假设条件下,有xp≤xq+1成立. 当i≥1时,设xp-j≤xq+1+j(0≤j≤i-1)已成立.若dT(up-j)=2,则yp-j=xp-j≤xq+1+j≤yq+1+j;若dT(up-j)=4,则由引理2可知从而有 于是,有yp-j≤yq+1+j(0≤j≤i-1)成立.因此, 即xp-i-xq+1+i≤xp-(i-1)-xq+i≤0,亦即xp-i≤xq+1+i也成立. 由数学归纳法可知,对于所有0≤i≤p,均有xp-i≤xq+1+i成立,从而有yp-i≤yq+1+i成立. 又因b≥a+2,则存在一个i0(0≤i0≤p),满足dT(up-i0)=2且dT(uq+1+i0)=4,于是,yp-i0=xp-i0≤xq+1+i0 假设x0≤xd,现利用数学归纳法证xi≤xd-i(0≤i≤p). 当i≥1时,设xj≤xd-j(0≤j≤i-1)已成立.由引理2可知,yj≤yd-j(0≤j≤i-1),因此, ρ(T)(xi-xd-i)-ρ(T)(xi-1-xd-(i-1))= 于是,xi-xd-i≤xi-1-xd-(i-1)≤0,因此,xi≤xd-i(0≤i≤p).特别地,xp≤xq+1,矛盾,所以,x0>xd,断言2成立. 在断言2成立的基础上,类似地,可用数学归纳法得,0 因b≥a+2,易得a+s≤p,a+t≤q,再根据结论c的证明过程可知所以 现证明xa+s-i>xa+t+1+i(0≤i≤s-1). 当i=0时, ρ(T)(xa+s-xa+t+1)= 故xa+s>xa+t+1成立. 当 1≤i≤s-1 时,设 xa+s-j>xa+t+1+j(0≤j≤i-1)已成立,即 ya+s- j>ya+t+1+j(0≤j≤i-1),则 ρ(T)(xa+s-i-xa+t+1+i)-ρ(T)(xa+s-(i-1)-xa+t+i)= 于是, xa+s-i-xa+t+1+i>xa+s-(i-1)-xa+t+i>0 (3) 从而xa+s-i>xa+t+1+i成立.由数学归纳法可知,对于所有0≤i≤s-1,均有xa+s-i>xa+t+1+i成立.再由式(3)得结论d成立. 综上,引理5成立.
4度点数固定的树的距离谱半径
