研究的图均为连通的简单无向图.设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∈
若X是D(G)的相应于λ的特征向量, 则对每一点u∈V(G), 有
(1) |
称式(1)为G在u点处的(λ, X)-特征方程.对于任意单位向量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), 等式成立当且仅当T(T)
推论1 设T是n(n≥5)阶树, 最大度Δ≥4, 则ρ(T)≤ρ(C(n, 0, 1)), 等式成立当且仅当T
证明 因为, Δ≥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<xi, 则xi<xi+1.
引理5 设图C(n, a, b)如图 1所示, b≥a+2≥2, 3(a+b)<n-2, r=n-3a-3b-2, X是它的距离Perron向量, 其分量xv与顶点v对应, 则有结论:
a. 0<xu0-xv0<xu1-xv1<…<xua-xva<xvb+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″,
c. 0<x0-xd<x1-xd-1<…<xa-xd-a<xa+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.
令
断言1 xp>xq+1.
假设
当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可知, xp-j′+xp-j″≤x′q+1+j+x″q+1+j, 从而有
于是, 有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<yq+1+i0, 从而
因此,
断言2 x0>xd.
假设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), 因此,
于是, xi-xd-i≤xi-1-xd-(i-1)≤0, 因此, xi≤xd-i(0≤i≤p).特别地, xp≤xq+1, 矛盾, 所以, x0>xd, 断言2成立.
在断言2成立的基础上, 类似地, 可用数学归纳法得, 0<xi-xd-i<xi+1-xd-(i+1)(0≤i≤a), 结论c成立.
现证明结论d.
因b≥a+2, 易得a+s≤p, a+t≤q, 再根据结论c的证明过程可知,
现证明xa+s-i>xa+t+1+i(0≤i≤s-1).
当i=0时,
故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), 则
于是,
(3) |
从而xa+s-i>xa+t+1+i成立.由数学归纳法可知, 对于所有0≤i≤s-1, 均有xa+s-i>xa+t+1+i成立.再由式(3)得结论d成立.
综上, 引理5成立.
定理1 设图C(n, a, b)如图 1所示, b+i≥a+2≥2x, 3(a+b)<n-2, r=n-3a-3b-2, 则
证明 令T=C(n, a, b), X=X(T)是它的距离Perron向量, 其分量xui, x′ui, x″ui分别对应顶点ui, ui′, ui″, 分量xvi, x′vi, x″vi分别对应顶点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, 所以, xvb<xvb-1.由引理4可知, xvb<xvb-1<…<xva+1<xva<…<xv1<xv0, 从而
(4) |
由引理2可知,
所以
从而
(5) |
令T′=T-{vbv′b, vbv″b}+{vb+rv′b, vb+rv″b}, 显然, T′
其中
现分两部分来证明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)的最小行和大于
若a≥1, 则对于1≤i≤a, 令Ui={ui, u′i, u″i}, Vi={vi, v′i, v″i}, 并令R={vb+1, …, vb+r}.
对于任意0≤j≤a, 有
若a≥1, 则对于任意1≤j≤a, 有
对于任意v∈R, 有
对于任意0≤j≤b, 有
对于任意1≤j≤b, 有
综上, 命题成立, 从而ρ(T′)>ρ(T), 定理1得证.
3 4度点数固定的树引入一种图的变换, 得到距离谱半径的变化规律(引理6).进一步, 研究4度点数固定的树集, 以及度至少为4的点数固定的树集, 刻画距离谱半径最大的极图(定理2和定理3).
引理6 设G21(s, t)如图 4所示, 其中, G1, G2为连通图, 且至少有1个是非平凡的.若t≥s≥2, 则有
证明 令G=G21(s, t), G3, G4分别是G-us的包含点u0和us+t的分支, 令
显然, G′
断言3 σG(G1)+σG(G2)-xu′s-1-xu″s-1>0.
因为, G1, G2中至少有1个非平凡分支, 不妨设G1是非平凡分支.选1点v∈V(G1), 满足
令d=dG(v, u′s), 因为V(G1)≥2, 所以, d≥1且v≠u′s.考虑在u′s, u″s, v, u′s-1, u″s-1处的(ρ(G), X)-特征方程, 可得
注意到w∈V(G)\(V(G1)∪V(G2)∪{u′s-1, u″s-1}), 有
且当w∈V(G1)\{u′s, v}时, dG(u″s, w)+dG(v, w)-dG(u′s, w)>0, 当w∈V(G2)\{u″s}时, dG(u′s, w)+dG(v, w)-dG(u″s, w)>0, 因此,
于是,
因此, 断言3成立.
断言4 σG(G4)≥σG(G3).
令yk=xuk+xu′k+xu″k(1≤k≤s+t-1), y0=xu0, ys+t=xus+t.假设σG(G3)>σG(G4), 即
当i=1时, ρ(G)(xus-1-xus+1)=2(
当2≤i≤s时, 设xus-j-xus+j<0 (1≤j≤i-1)已成立, 由引理2可知, ys-j-ys+j<0 (1≤j≤i-1), 从而
所以, xus-i-xus+i<xus-(i-1)-xus+(i-1)<0.
由数学归纳法可知, 对于所有1≤i≤s, 均有xus-i-xus+i<0成立.
于是, 对所有1≤i≤s, 也有ys-i-ys+i<0, 从而,
根据2个断言可得,
引理7 设T是n(n≥5)阶毛毛虫图, Δ(T)=4, 且4度点的个数为k,
证明 设T*为满足引理7所给条件的距离谱半径最大的毛毛虫图, 令t为T*中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度点, 不妨设x∈V(T1), y∈V(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,
定理2 设T∈T(n, k), 则
证明 当k=1时, 由推论1可知结论成立.现考虑k≥2的情况, 设T*为T(n, k)中距离谱半径最大的树.
断言5 T*的最大偶度等于4.
否则, T*的最大偶度大于或等于6, 不妨设dT*(u)=2t且t≥3.令NT*(u)={u1, …, u2t}, Ti为T*-u的含有点ui(1≤i≤2t)的分支.不失一般性, 设σT*(T2t)≤σT*(T1), 令v为V(T2t)中的1个悬挂点, T=T*-uu2+vu2, T中4度点的个数仍为k, 即T∈T(n, k), 但由引理3可知, ρ(T)>ρ(T*), 矛盾.
断言6 T*的奇度点均为悬挂点.
现通过2种假设反正断言6.
a.假设T*的最大奇度大于或等于5, 不妨设dT*(u)=2t+1且t≥2.令NT*(u)={u1, …, u2t+1}, Ti为T*-u的含有点ui(1≤i≤2t+1)的分支.不失一般性, 设σT*(T2t+1)≤σT*(T1), 令v为V(T2t+1)中的1个悬挂点, T=T*-{uu2, uu3}+{vu2, vu3}, 注意到T∈T(n, k), 但由引理3可知, ρ(T)>ρ(T*), 矛盾.
b.假设T*的最大奇度等于3, 不妨设dT*(u)=3.令NT*(u)={u1, u2, u3}, Ti为T-u的含有点ui(i=1, 2, 3)的分支.不失一般性, 设σT*(T3)≤σT*(T1), 令v为V(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.对于任意u∈U, 仍有dT*(u)=4, 令NT*(u)={u1, u2, u3, u4}, dT*(ui)≥2, i=1, 2, 3.再令Ti为T*-u的含有点ui(i=1, 2, 3, 4)的分支, 则T*的2度点必全属于某个V(Ti), i∈{1, 2, 3, 4}.若不然, 存在度为2的2个点, 1个在V(Ti)中, 1个在V(Tj)中, i≠j, 不妨设dT*(v1)=dT*(v3)=2, v1∈V(T1), v3∈V(T3), 不失一般性, 再设σT*(T3)≤σT*(T1).令T=T*-{uu2, uu4}+{v3u2, v3u4}, 则T∈T(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, 不妨设t≥s≥2.令T=G21(s-1, t+1), 则T∈T(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 设T是n(n≥5)阶树, 其中, 度至少为4的点数为k,
证明当k=1时, 由推论1可知结论成立, 以下考虑k≥2情况.
设T*是满足定理3条件的距离谱半径最大的树.假设Δ(T*)≥5, 不妨设NT*(u)={u1, …, uΔ}, 令Ti为T*-u的含有点ui(i=1, …, Δ)的分支.不失一般性, 设σT*(TΔ)≤σT*(T1), 令T=T*-{uui:2≤i≤Δ-1}+{wui:2≤i≤Δ-1}, 其中, w为T*的属于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. |