加权冠图的无符号拉普拉斯谱和正规拉普拉斯谱

魏 斌，王维忠

兰州交通大学 数理学院，兰州 730070

众所周知，许多复杂系统，如社会系统、生物系统等，均可用复杂网络来描述，而任何复杂网络都可用图来表示.因此，关于复杂网络的研究一直是图论领域中的热点问题.相比较无权网络只考虑节点间相互作用的存在与否，加权网络的权还能刻画该网络所描述实际系统中个体间相互作用的强度，因此加权网络更能准确地描述实际网络[1].例如，机场网络[1]中每年在两个机场之间旅行的乘客人数，网络[2]中路由器之间单位时间内的数据包流量，以及生态系统[3]中捕食者——被捕食者相互作用的强度等都可通过权来反映.虽然目前关于冠图的成果很多[4-8]，但关于加权冠图的研究十分鲜见.文献[9]刻画了G2为d-正则图和完全二部图时加权冠图G1∘G2的邻接特征值，同时得到了当G2是连通图时图G1∘G2的拉普拉斯特征值.文献[10]中给出了G2为d-正则图和完全二部图时加权边冠图G1◇G2的邻接特征值和(无符号)拉普拉斯特征值.

受上述研究的启发，本文刻画了当G2为正则图时，加权冠积图G1∘G2的无符号拉普拉斯谱，以及G1和G2都为正则图时，G1∘G2的正规拉普拉斯谱.借助数学归纳法，把关于G1∘G2的结果加以推广，得到了加权冠图G(m)的无符号拉普拉斯谱和正规拉普拉斯谱.下面，首先给出加权冠积图[9]的定义.

定义1设G1和G2是阶数分别为n和k的简单连通图，将G1复制一次且每条边的权数为1，G2对应于G1的顶点复制n次且每条边的权数为r(0

例如，设G1为4个顶点的圈，G2为3个顶点的完全图，则加权冠积图G1∘G2如图1(c)所示.

图1 图G1，G2及其加权冠积图G1∘G2

1 G1∘G2的无符号拉普拉斯谱

设R⊗S表示矩阵R和S的克罗内克积，由G1∘G2的定义，可得G1∘G2的无符号拉普拉斯矩阵为

(1)

定理1设G1是n阶的简单连通图，G2是k阶的d-正则图.σ(G1)={θ1，θ2，…，θn}，σ(G2)={νi|ν1≤ν2≤…≤νk=2d}.则Q(G1∘G2)的特征值为：

Q(G1∘G2)X=ξX

(2)

下面我们分两种情形进行讨论.

情形1X1为非零向量.

由(1)式和(2)式得

(Q(G1)+rkIn)X1+r(X2+X3+…+Xk+1)=ξX1

(3)

和

(4)

因为G2是d-正则图，则Q(G2)矩阵的每行元素之和为2d.将(4)式中的所有方程相加，可得

krX1+r(2d+1)(X2+X3+…+Xk+1)=ξ(X2+X3+…+Xk+1)

(5)

移项得

krX1+((2d+1)r-ξ)(X2+X3+…+Xk+1)=0

(6)

由于X1是非零向量，我们推出(2d+1)r-ξ≠0.由(3)式和(6)式，得

(7)

即

(8)

ξ2-((2d+1)r+kr+θi)ξ-kr2+(2d+1)kr2+(2d+1)rθi=0i=1，2，…，n

(9)

解二次方程(9)，得

(10)

情形2X1为零向量.

由(1)式和(2)式得

X1+X2+…+Xk+1=0

(11)

和

r(Q(G2)+Ik)⊗In[X2X3…Xk+1]T=ξ[X2X3…Xk+1]T

(12)

故r(2d+1)不是Q(G1∘G2)的特征值.如若不然，假定r(2d+1)是Q(G1∘G2)的特征值，则r(2d+1)对应的特征向量X=[X1X2…Xk+1]T满足X=Jn⊗Jk+1.因此

X1+X2+…+Xk+1=(k+1)Jn

(13)

这与(11)式相矛盾.所以

ξ=r(νj+1)j=1，2，…，k-1

(14)

从(12)式可以看出ξ=r(νj+1)的重数为n.

2 G1∘G2的正规拉普拉斯谱

正规拉普拉斯矩阵和图G上的简单随机途径与谱的几何结构密切相关.给定一个图G，令P(G)=D(G)-1A(G)表示G上的简单随机游动的概率转移矩阵，则

(15)

设L(G)和P(G)的谱分别为λ1(G)，λ2(G)，…，λn(G)和μ1(G)，μ2(G)，…，μn(G).其中0=λ1(G)≤λ2(G)≤…≤λn(G)≤2，1=μ1(G)≥μ2(G)≥…≥μn(G)≥-1.则

λi(G)=1-μi(G)i=1，2，…，n

(16)

有关正规拉普拉斯谱的详细信息可参见文献[11].

设G1和G2分别为n1阶和n2阶正则连通图，且正则度分别为r1和r2，则

(17)

(18)

由于G1和G2都是正则图，故

从而

(19)

由(15)式知，在刻画G1∘G2的正规拉普拉斯谱时，首先给出概率转移矩阵P(G1∘G2)的谱.

定理2设G1和G2分别是阶数为n1和n2的正则连通图，正则度分别为r1和r2，P(G1)的谱为μ1(=1)，μ2，…，μn1，P(G2)的谱为η1(=1)，η2，…，ηn2.则P(G1∘G2)的谱为：

(20)

(21)

因此，若两个实数pi和a满足

(22)

(23)

则P(G1∘G2)的属于特征值pi的特征向量为

由(23)式得

(24)

由(22)式和(24)式得

(25)

其中

根据定理2和(16)式，即得出G1∘G2的正规拉普拉斯谱：

定理3设G1和G2分别是阶数为n1和n2的正则连通图，正则度分别为r1和r2，L(G1)的谱为λ1(=0)，λ2，…，λn1，L(G2)的谱为δ1(=0)，δ2，…，δn2.则L(G1∘G2)的谱为：

3 G(m)的无符号拉普拉斯谱和正规拉普拉斯谱

本节中，我们将推广加权冠积图得到加权冠图的无符号拉普拉斯谱和正规拉普拉斯谱.首先，定义加权冠图[9]如下：

定义2设G是n阶的简单连通图，且每条边的权都为1，G′为G的复制图.加权冠图G(m)定义为G(m)=G(m-1)∘G′，新生成的边的权为rm(其中m≥1是自然数).

例如，设G=K3(3个顶点的完全图)(图2(a))，则加权冠图G(1)和G(2)分别如图2(b)和2(c)所示.

图2 图G及其加权冠图G(1)和G(2)

其中j=1，2，…，且f0(x)=x+1.

接下来给出当G为d-正则图时，加权冠图G(m)的无符号拉普拉斯谱.

定理4设G是n阶d-正则图，σ(G)={θ1，θ2，…，θn}，则

σ(G(m))={rm-jfj(θi)|0≤j≤m-1，i=1，2，…，n-1；j=m，i=1，2，…，n}

其中：

j=1，2，…；f0(x)=x+1；rm-jfj(θi)∈σ(G(m))的重数为n(n+1)m-j-1，0≤j≤m-1；fm(θi)∈σ(G(m))的重数为1.

证用数学归纳法进行证明.

其中

最后，刻画了G为d-正则图时，G(m)的正规拉普拉斯谱：

定理5设G是n阶d-正则图，L(G)的谱为λ1，λ2，…，λn，则L(G(m))的谱为

{rm-jgj(λi)|0≤j≤m-1，i=1，2，…，n-1；j=m，i=1，2，…，n}

其中

证同定理4.

4 结 语

本文主要研究了加权冠图的无符号拉普拉斯谱和正规拉普拉斯谱.具体来讲，刻画了当G2为正则图时，加权冠积图G1∘G2的无符号拉普拉斯谱，以及G1和G2都为正则图时，G1∘G2的正规拉普拉斯谱.并借助数学归纳法将关于G1∘G2的结果加以推广，给出了加权冠图G(m)的无符号拉普拉斯谱和正规拉普拉斯谱.所得结论进一步丰富了图谱理论和加权网络研究方面的成果.