上海理工大学学报  2017, Vol. 39 Issue (5): 409-415   PDF    
4度点数固定的树的距离谱半径
汪云, 吴宝丰     
上海理工大学 理学院, 上海 200093
摘要: 引入了一种图的变换,得到了距离谱半径的变化规律.进一步研究了四度点数固定的树集,刻画了该图类中距离谱半径最大的极图.最后,讨论了更一般的图类,即度至少为4的点数固定的树集,并确定了极图.
关键词: 距离矩阵     距离谱半径     距离Perron向量         
Distance Spectral Radius of Trees with Given Number of Vertices of Degree 4
WANG Yun, WU Baofeng     
College of Science, University of Shanghai for Science and Technology, Shanghai 200093, China
Abstract: A graph transformation was introduced to show the effect of the distance spectral radius.Further, the set of trees with given number of vertices of degree 4 was studied, characterizing the extremal graph with the largest distance spectral radius.Finally, the more general class of graphs, namely, the set of trees with given number of vertices of degree at least 4 was discussed, and also its extremal graph was characterized.
Key words: distance matrix     distance spectral radius     distance Perron vector     tree    
1 基本概念

研究的图均为连通的简单无向图.设Gn阶连通图, V(G)和E(G)分别是顶点集和边集.对于任意顶点vV(G), 用NG(v)表示它的邻集, 并根据其度数的奇偶性, 称它为奇度点或偶度点.对于图G的任意2点u, v, 用dG(u, v)表示它们的距离, D(G)=(dG(u, v))u, vV(G)表示图G的距离矩阵.显然, D(G)是实对称的, 所以, 它的特征值全为实数.图G的距离谱半径用ρ(G)表示, 代表D(G)的最大特征值.连通图对应的距离矩阵是不可约的, 由Perron-Frobenius定理可知, ρ(G)是单根, 且有相应的正单位特征向量, 记为X(G), 称为G的距离Perron向量.

任取向量X=(x1, …, xn)T (这里X可能是G的距离Perron向量, 也可能不是), 可将它的分量与G中的点一一对应, 即分量xi对应顶点vi, 则

XD(G)的相应于λ的特征向量, 则对每一点uV(G), 有

(1)

称式(1)为Gu点处的(λ, X)-特征方程.对于任意单位向量X, 由Rayleigh-Ritz定理[1], 有

XG的距离Perron向量时, 上式等号成立.对于G的子图H, 记σG(H)为G的距离Perron向量中对应于V(H)的所有分量之和.

Pn表示n阶路, 它是n阶连通图中距离谱半径最大的图[2].若一棵树, 将其所有悬挂点删去后所得图是一条路, 则称该树为毛毛虫图.显然, Pn自身也是毛毛虫图.

V1V(G), 则G-V1表示将图G删去V1中的点以及相关联的所有边后所得到的图.若V1={u}, 则用G-u来代替G-{u}.对于E1E(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    设ba≥0, 3(a+b)≤n-2, r=n-3a-3b-2, 记图 1所示的图为C(n, a, b).特别地, C(n, 0, 0)是路Pn.


图 1 C(n, a, b) Fig. 1 C(n, a, b)

定义2    设2≤Δn-1, 路Pn-Δ+1的1个端点连接Δ-1个悬挂点所得到的图记为Bn, Δ图 2所示.


图 2 Bn, Δ Fig. 2 Bn, Δ

引理1[7]    设Tn(n≥4)阶树, Δ为最大度, 则ρ(T)≤ρ(Bn, Δ)(T), 等式成立当且仅当T(T)Bn, Δ.进一步, 若Δ1>Δ2, 则ρ(Bn, Δ1)<ρ(Bn, Δ2).

推论1    设Tn(n≥5)阶树, 最大度Δ≥4, 则ρ(T)≤ρ(C(n, 0, 1)), 等式成立当且仅当TC(n, 0, 1).

证明    因为, Δ≥4, 由引理1可知, ρ(T)≤ρ(Bn, Δ)≤ρ(Bn, 4)=ρ(C(n, 0, 1)), 等号成立当且仅当T=C(n, 0, 1), 证毕.

引理2[7]    设Gn阶连通图, XG的距离Perron向量, 其分量xv与顶点v对应.令u, vV(G), u′, v′分别是u, v的悬挂邻点, 则xu′-xv′=.

引理3[6]    设T是树, uV(T), NT(u)={u1, …, uk}, 其中, k≥3, TiT-u的包含ui(1≤ik)的分支, wV(Tk), 对于任意t=2, 3, …, k-1, 令T′=T-{uui:2≤it}+{wui:2≤it}.若σT(Tk)≤σT(T1), 则ρ(T′)>ρ(T).

引理4[8]    设Gn阶连通图, X=(x1, x2, …, xn)TG的距离Perron向量, 其分量xi与顶点vi对应.令vi-1vi, vivi+1G的2条边, 且vi-1vi, vivi+1中至少有1条是割边, 若xi-1xi, 则xixi+1.

引理5    设图C(n, a, b)如图 1所示, ba+2≥2, 3(a+b)<n-2, r=n-3a-3b-2, X是它的距离Perron向量, 其分量xv与顶点v对应, 则有结论:

a. 0<xu0-xv0xu1-xv1<…<xua-xvaxvb+r-xva+1;

b. xvb+r-i-xvb+i>xvb+r-(i+1)-xvb+(i+1)>0 .

证明    设图C(n, a, b)的直径为d, 对图 1进行重新编号, 如图 3所示, 并设X的分量xi, x′i, xi″分别对应顶点ui, ui′, ui″, , , 则结论a和b转化为结论c和d.


图 3 重新编号的C(n, a, b) Fig. 3 Renumbered C(n, a, b)

c. 0<x0-xdx1-xd-1<…<xa-xd-axa+1-xd-(a+1);

d. 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.

, , 且对于任意i=0, 1, …, d, 令

断言1    xp>xq+1.

假设, 用数学归纳法可推出xp-ixq+1+i(0≤ip).

i=0时, 由式(1)可知,

(2)

在假设条件下, 有xpxq+1成立.

i≥1时, 设xp-jxq+1+j(0≤ji-1)已成立.若dT(up-j)=2, 则yp-j=xp-jxq+1+jyq+1+j; 若dT(up-j)=4, 则由引理2可知, xp-j′+xp-j″≤xq+1+j+xq+1+j, 从而有

于是, 有yp-jyq+1+j(0≤ji-1)成立.因此,

xp-i-xq+1+ixp-(i-1)-xq+i≤0, 亦即xp-ixq+1+i也成立.

由数学归纳法可知, 对于所有0≤ip, 均有xp-ixq+1+i成立, 从而有yp-iyq+1+i成立.

又因ba+2, 则存在一个i0(0≤i0p), 满足dT(up-i0)=2且dT(uq+1+i0)=4, 于是, yp-i0=xp-i0xq+1+i0yq+1+i0, 从而, 与假设矛盾.

因此, , 根据式(2), 有xp>xq+1, 断言1成立.

断言2    x0>xd.

假设x0xd, 现利用数学归纳法证xixd-i(0≤ip).

i≥1时, 设xjxd-j(0≤ji-1)已成立.由引理2可知, yjyd-j(0≤ji-1), 因此,

于是, xi-xd-ixi-1-xd-(i-1)≤0, 因此, xixd-i(0≤ip).特别地, xpxq+1, 矛盾, 所以, x0>xd, 断言2成立.

在断言2成立的基础上, 类似地, 可用数学归纳法得, 0<xi-xd-ixi+1-xd-(i+1)(0≤ia), 结论c成立.

现证明结论d.

ba+2, 易得a+sp, a+tq, 再根据结论c的证明过程可知, , 所以

现证明xa+s-i>xa+t+1+i(0≤is-1).

i=0时,

xa+s>xa+t+1成立.

当1≤is-1时, 设xa+s-j>xa+t+1+j(0≤ji-1)已成立, 即ya+s-j>ya+t+1+j(0≤ji-1), 则

于是,

(3)

从而xa+s-i>xa+t+1+i成立.由数学归纳法可知, 对于所有0≤is-1, 均有xa+s-i>xa+t+1+i成立.再由式(3)得结论d成立.

综上, 引理5成立.

定理1    设图C(n, a, b)如图 1所示, b+ia+2≥2x, 3(a+b)<n-2, r=n-3a-3b-2, 则

证明    令T=C(n, a, b), X=X(T)是它的距离Perron向量, 其分量xui, xui, xui分别对应顶点ui, ui′, ui″, 分量xvi, xvi, xvi分别对应顶点vi, vi′, vi″, 令

T1, T2分别是T删去vb所得的含有点u0, v0的分支, 当σT(T1)≤σT(T2)时, 由引理3可知, 结论显然成立.当σT(T1)>σT(T2)时, ρ(T)·(xvb-xvb-1)=σ(T2)-(σ(T1)+zb)<0, 所以, xvbxvb-1.由引理4可知, xvbxvb-1<…<xva+1xva<…<xv1xv0, 从而

(4)

由引理2可知,

所以

从而

(5)

T′=T-{vbvb, vbvb}+{vb+rvb, vb+rvb}, 显然, TC(n, a+1, b-1).考虑

其中

现分两部分来证明w>0.

a.要证ρ(T′)>ρ(T), 只需证w>0.由引理2和引理5的a可得

(6)

于是, 由引理5的b及式(4)~(6)可得

因此

b.由引理5的b可知, xvb+r-xvb>0, 由Perron-Frobenius定理可知, 不可约非负矩阵的谱半径大于等于最小行和, 故要证w>0, 只需证下面的命题.

命题    D(T)的最小行和大于 +(3a+1)r.

a≥1, 则对于1≤ia, 令Ui={ui, ui, ui}, Vi={vi, vi, vi}, 并令R={vb+1, …, vb+r}.

对于任意0≤ja, 有

a≥1, 则对于任意1≤ja, 有

对于任意vR, 有

对于任意0≤jb, 有

对于任意1≤jb, 有

综上, 命题成立, 从而ρ(T′)>ρ(T), 定理1得证.

3 4度点数固定的树

引入一种图的变换, 得到距离谱半径的变化规律(引理6).进一步, 研究4度点数固定的树集, 以及度至少为4的点数固定的树集, 刻画距离谱半径最大的极图(定理2和定理3).

引理6    设G21(s, t)如图 4所示, 其中, G1, G2为连通图, 且至少有1个是非平凡的.若ts≥2, 则有


图 4 G21(s, t) Fig. 4 G21(s, t)

证明    令G=G21(s, t), G3, G4分别是G-us的包含点u0us+t的分支, 令

显然, GG21(s-1, t+1).令X=X(G)为图G的距离Perron向量, 从GG′, V(G1)∪V(G2)中的点到V(G3)\{us-1, us-1}中的点的距离减少1, V(G1)∪V(G2)中的点到V(G4)∪{us}中的点的距离增加1, us-1, us-1V(G3)\{us-1, us-1}中的点的距离增加1, us-1, us-1V(G4)∪{us}中的点的距离减少1, 其他点之间的距离保持不变, 因此,

断言3    σG(G1)+σG(G2)-xus-1-xus-1>0.

因为, G1, G2中至少有1个非平凡分支, 不妨设G1是非平凡分支.选1点vV(G1), 满足

d=dG(v, us), 因为V(G1)≥2, 所以, d≥1且vus.考虑在us, us, v, us-1, us-1处的(ρ(G), X)-特征方程, 可得

注意到wV(G)\(V(G1)∪V(G2)∪{us-1, us-1}), 有

且当wV(G1)\{us, v}时, dG(us, w)+dG(v, w)-dG(us, w)>0, 当wV(G2)\{us}时, dG(us, w)+dG(v, w)-dG(us, w)>0, 因此,

于是,

因此, 断言3成立.

断言4    σG(G4)≥σG(G3).

yk=xuk+xuk+xuk(1≤ks+t-1), y0=xu0, ys+t=xus+t.假设σG(G3)>σG(G4), 即, 现证明, xus-i-xus+i<0 (1≤is).

i=1时, ρ(G)(xus-1-xus+1)=2()<0, 所以, xus-1-xus+1<0成立.

当2≤is时, 设xus-j-xus+j<0 (1≤ji-1)已成立, 由引理2可知, ys-j-ys+j<0 (1≤ji-1), 从而

所以, xus-i-xus+ixus-(i-1)-xus+(i-1)<0.

由数学归纳法可知, 对于所有1≤is, 均有xus-i-xus+i<0成立.

于是, 对所有1≤is, 也有ys-i-ys+i<0, 从而, , 与假设矛盾.因此, 断言4成立.

根据2个断言可得, (ρ(G′)-ρ(G))>0, 即ρ(G′)>ρ(G), 亦即ρ(G21(s-1, t+1))>ρ(G21(s, t)).

引理7    设Tn(n≥5)阶毛毛虫图, Δ(T)=4, 且4度点的个数为k, , 奇度点均为悬挂点, 则, 等式成立当且仅当.

证明    设T*为满足引理7所给条件的距离谱半径最大的毛毛虫图, 令tT*中2度点的个数, 按下面2种情形讨论.

情形1    t≤1.

此时T*形如C(n, a, b), 由定理1可知, .

情形2    t≥2.

对于任意4度点u, T*-u至少有2个孤立点分支, 记为v1, v2, 另外, 2个分支记为T1, T2.假设T1, T2中均有2度点, 不妨设xV(T1), yV(T2), dT*(x)=dT*(y)=2, 不失一般性, 再设σT*(T2)≤σT*(T1), 则令T=T*-{uv1, uv2}+{yv1, yv2}, T仍满足引理7所给条件, 但由引理3可知, ρ(T)>ρ(T*), 与T*的定义矛盾.于是, T*中的2度点全在T1中或全在T2中, 故T*形如C(n, a, b), 由定理1可知, .

综上, 引理7成立.

定义3    对于整数n, k, 满足n≥5, , 记T(n, k)表示恰含k个4度点的n阶树的集合.

定理2    设TT(n, k), 则, 等式成立当且仅当.

证明    当k=1时, 由推论1可知结论成立.现考虑k≥2的情况, 设T*T(n, k)中距离谱半径最大的树.

断言5    T*的最大偶度等于4.

否则, T*的最大偶度大于或等于6, 不妨设dT*(u)=2tt≥3.令NT*(u)={u1, …, u2t}, TiT*-u的含有点ui(1≤i≤2t)的分支.不失一般性, 设σT*(T2t)≤σT*(T1), 令vV(T2t)中的1个悬挂点, T=T*-uu2+vu2, T中4度点的个数仍为k, 即TT(n, k), 但由引理3可知, ρ(T)>ρ(T*), 矛盾.

断言6    T*的奇度点均为悬挂点.

现通过2种假设反正断言6.

a.假设T*的最大奇度大于或等于5, 不妨设dT*(u)=2t+1且t≥2.令NT*(u)={u1, …, u2t+1}, TiT*-u的含有点ui(1≤i≤2t+1)的分支.不失一般性, 设σT*(T2t+1)≤σT*(T1), 令vV(T2t+1)中的1个悬挂点, T=T*-{uu2, uu3}+{vu2, vu3}, 注意到TT(n, k), 但由引理3可知, ρ(T)>ρ(T*), 矛盾.

b.假设T*的最大奇度等于3, 不妨设dT*(u)=3.令NT*(u)={u1, u2, u3}, TiT-u的含有点ui(i=1, 2, 3)的分支.不失一般性, 设σT*(T3)≤σT*(T1), 令vV(T3)中的1个悬挂点, T=T*-uu2+vu2, T中4度点的个数仍为k, 由引理3可知, ρ(T)>ρ(T*), 矛盾.

综合a和b, 断言6成立, 从而T*中点的度只有3种情况:1, 2或4.

断言7    T*是毛毛虫图.

否则, 设T×是将T*中所有悬挂点删去后所得的图, 则至少存在1个点, 在图T×中的度为3或4, 将这些点构成的集合记为U.对于任意uU, 仍有dT*(u)=4, 令NT*(u)={u1, u2, u3, u4}, dT*(ui)≥2, i=1, 2, 3.再令TiT*-u的含有点ui(i=1, 2, 3, 4)的分支, 则T*的2度点必全属于某个V(Ti), i∈{1, 2, 3, 4}.若不然, 存在度为2的2个点, 1个在V(Ti)中, 1个在V(Tj)中, ij, 不妨设dT*(v1)=dT*(v3)=2, v1V(T1), v3V(T3), 不失一般性, 再设σT*(T3)≤σT*(T1).令T=T*-{uu2, uu4}+{v3u2, v3u4}, 则TT(n, k), 但由引理3可知, ρ(T)>ρ(T*), 矛盾.故不妨设T*的2度点全属于V(T1).

现分2种情形讨论.

情形1    |U\V(T1)|=1.

此时U\V(T1)={u}, T*形如G21(s, t), 且t, s≥2, 不妨设ts≥2.令T=G21(s-1, t+1), 则TT(n, k), 由引理6可知, ρ(T)>ρ(T*), 矛盾.

情形2    |U\V(T1)|>1.

u′U\V(T1)中距离u最远的点, 此时u′可看作情形1中的u, 类似地, 可推出矛盾.

综合情形1和2, 断言7成立.

因此, T*是1个最大度为4且奇度点均为悬挂点的毛毛虫图, 结合引理7, 可知, 结论得证.

定理3    设Tn(n≥5)阶树, 其中, 度至少为4的点数为k, , 则, 等式成立当且仅当.

证明当k=1时, 由推论1可知结论成立, 以下考虑k≥2情况.

T*是满足定理3条件的距离谱半径最大的树.假设Δ(T*)≥5, 不妨设NT*(u)={u1, …, uΔ}, 令TiT*-u的含有点ui(i=1, …, Δ)的分支.不失一般性, 设σT*(TΔ)≤σT*(T1), 令T=T*-{uui:2≤iΔ-1}+{wui:2≤iΔ-1}, 其中, wT*的属于V(TΔ)的悬挂点.易知T仍满足题设条件, 由引理3可知, ρ(T)>ρ(T*), 矛盾.所以, T*T(n, k), 结合定理2, 定理3得证.

参考文献
[1] HORN R A, JOHNSON C R. Matrix analysis[M]. Cambridge: Cambridge University Press, 1985.
[2] STEVANOVIĆD, ILIĆ A. Distance spectral radius of trees with fixed maximum degree[J]. Electronic Journal of Linear Algebra, 2010, 20(1): 168–179.
[3] CAYLEY A. A theorem in the geometry of position[J]. The Cambridge Mathematical Journal, 1841, 2: 267–271.
[4] GRAHAM R L, POLLAK H O. On the addressing problem for loop switching[J]. Bell System Technical Journal, 1971, 50(8): 2495–2519. DOI:10.1002/bltj.1971.50.issue-8
[5] AOUCHICHE M, HANSEN P. Distance spectra of graphs:a survey[J]. Linear Algebra and its Applications, 2014, 458(2): 301–386.
[6] LIN H Y, ZHOU B. The distance spectral radius of graphs with given number of odd vertices[J]. Electronic Journal of Linear Algebra, 2016, 31(1): 286–305. DOI:10.13001/1081-3810.2877
[7] WANG Y N, ZHOU B. On distance spectral radius of graphs[J]. Linear Algebra and its Applications, 2013, 438(8): 3490–3503. DOI:10.1016/j.laa.2012.12.024
[8] RUZIEH S N, POWERS D L. The distance spectrum of the path Pn and the first distance eigenvector of connected graphs[J]. Linear Multilinear Algebra, 1990, 28(1/2): 75–81.