剖分-点联图和剖分-边联图的Kirchhoff指标

马婷妍，王维忠

(兰州交通大学 数理学院， 甘肃 兰州 730030)

1993年，Klein等[1]提出了图的电阻距离的概念。将图G的每条边用一个固定电阻代替，则对应得到电网络N，图G的顶点i和j之间的电阻距离rij等于电网络N中节点i和j之间的有效电阻，其求解过程遵循基尔霍夫法则和欧姆定律。Kirchhoff指标Kf(G)定义为图G的所有顶点对之间的电阻距离之和。1996年，Gutman[2]和Zhu[3]等分别证明了图的Kirchhoff指标与其拉普拉斯特征值之间的如下关系：

Kirchhoff指标是分子结构描述符，是一个重要的拓扑指标，关于它的研究已有很多成果[4-13]，其中文献[13]研究了R-点联和R-边联图的Kirchhoff指标。受此启发，本文考虑剖分-点联和剖分-边联图的Kirchhoff指标。

本文仅考虑简单的无向图。设图G=(V,E)的顶点集和边集分别为V={1,2,…,n}和E={e1,e2,…,em}，并设DG=diag(d1,d2,…,dn)是图G的度对角矩阵，其中di(1≤i≤n)为顶点i的度。图G的邻接矩阵AG=(aij)n×n定义如下：若顶点i和j相邻，则aij=1；否则aij=0。图G的Laplacian矩阵LG=DG-AG，其特征值为μ1≥μ2≥…≥μn=0(LG特征值的多重集就称作图G的Laplacian谱)。设BG=(bij)n×m是图G的点-边关联矩阵，若顶点i与边ej关联，则bij=1；否则bij=0。

1 预备知识

为了方便，设Jn×n表示元素均为1的n阶矩阵，1表示元素均为1的列向量。

图1 G1=G2=P2时的剖分图、剖分-点联图及剖分-边联图

引理2[14]设G1为n1个顶点m1条边的d-正则图，G2为n2阶图，则G1和G2的剖分-边联图G1G2的Laplacian矩阵的{1}-可逆矩阵为

其中l(G1)为G1的线图。

引理3[15]设G为n阶连通图，则Kf(G)=ntr(L(1)(G))-1TL(1)(G)1。

2 主要结果

证明由引理1可得

(1)

tr(A-1DG1)+tr(A-1AG1)，

(2)

(3)

同理可得

(4)

将式(2)—(4)带入式(1)可得

(5)

由引理1同时可得

(6)

由于BG11=π，所以

(7)

又因为

(8)

(9)

(10)

同样地，(LG2+n1I)-11=n11表明

(11)

将式(7)—(11)代入式(6)可得

(12)

结合式(5)和式(12)，由引理3可得定理2.1。

在定理2.1中，若G1为正则图，则可得推论2.2。

其次，当G1为正则图时，得到如下关于剖分-边联图G1G2的Kirchhoff指标计算公式。

定理2.3 设G1为n1个点m1条边的d-正则图，则G1和G2的剖分-边联图G1G2的Kirchhoff指标为

其中l(G1)为G1的线图。

证明由引理2可得

dtr((Ll(G1)+dn2I)-1)+(2+n2)tr((LG1+dn2I)-1)+

(13)

下面计算式(13)中的每一项，注意到矩阵Ll(G1)+dn2I和LG2+dn2I的拉普拉斯特征值分别为μ1(l(G1))+dn2，…，μm1(l(G1))+dn2和μ1(G1)+dn2，…，μn1(G1)+dn2，故可得

(14)

同理可得

将式(14)—(16)代入式(13)可得

另一方面

(18)

现计算上式中的每一项，由1T(Ll(G1)+dn2I)=dn21T可得

(19)

同理可得

(20)

(21)

(22)

类似地，由(LG2+m1I)-11=m11可得

(23)

将式(19)—(23)代入式(18)可得

(24)

结合式(17)和式(24)，由引理3可得定理2.3。

3 应用实例

这进一步验证了定理2.1以及推论2.2中结论的正确性。

例2 设G1=G2=P2，则图1(d)P2P2的Kirchhoff指标Kf(P2P2)=38/3。

容易知道P2的拉普拉斯特征值为0和2，而其线图的拉普拉斯特征值为0。于是由定理2.2可得图P2P2的Kirchhoff指标Kf(P2P2)=38/3。

另一方面，经计算可得图P2P2的Laplacian矩阵的{1}-可逆矩阵

由引理3可计算图P2P2的Kirchhoff指标

这进一步验证了定理2.1以及推论2.2中结论的正确性。

4 结 语

本文主要借助图的Laplacian矩阵的广义逆矩阵，给出了两个图的剖分-点联图与剖分-边联图的Kirchhoff指标计算公式，并通过两个简单的实例验证了所得结果的正确性。