,

(上海理工大学 理学院,上海 200093)

4度点数固定的树的距离谱半径

汪云,吴宝丰

(上海理工大学 理学院,上海200093)

引入了一种图的变换,得到了距离谱半径的变化规律.进一步研究了四度点数固定的树集,刻画了该图类中距离谱半径最大的极图.最后,讨论了更一般的图类,即度至少为4的点数固定的树集,并确定了极图.

距离矩阵; 距离谱半径; 距离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中的点以及相……