两类交叉四角链的拉普拉斯谱及其应用

2021-11-15涂淑玲王广富

华东交通大学学报 2021年5期

涂淑玲，王广富

（华东交通大学理学院，江西南昌 330013）

在图论中，拉普拉斯矩阵是图的一种矩阵表示，定义为图的度矩阵与邻接矩阵的差。拉普拉斯矩阵的所有特征值称为图的拉普拉斯谱。拉普拉斯谱及其应用可以解决复杂网络中的许多理论问题[1-2]，网络的拉普拉斯谱的计算在拓扑结构和动力学等方面有诸多应用。例如，在化学上，对于用来反映化合物分子结构的基尔霍夫指标已有广泛的研究。 1993 年，Klein 等[3]提出了一个新的距离函数——电阻距离。图的每条边等价于一个单位电阻，然后利用欧姆定律计算出任意两个顶点之间的有效电阻，即电阻距离；图中所有顶点对之间的电阻距离之和定义为图的基尔霍夫指标。网络的基尔霍夫指标可以用非零拉普拉斯特征值的倒数之和来表示[4]；网络的生成树数目可以由所有非零拉普拉斯特征值的乘积来确定[5]；网络的直径可以由拉普拉斯矩阵的第二小特征值来估算[6]。尽管从分析的角度，拉普拉斯谱的计算只是一个理论上的挑战，但建立网络的拉普拉斯谱是很有意义的。近二十年来，有很多人在研究各类分子图的拉普拉斯谱的计算及其应用[3，4，7-11]。 Yang等[12]研究了线性六角链的部分拉普拉斯特征值，从而确定了其基尔霍夫指标。之后，人们通过Yang 等[12]的方法得到了其他一些分子网络的部分拉普拉斯特征值及基尔霍夫指标，如苯环[13]、五边形链[14]等。 Pan 等[15]研究了线性交叉多联骨牌链（即线性交叉四角链) 的部分拉普拉斯特征值、基尔霍夫指标及生成树数目。直接计算出某图类的所有的拉普拉斯特征值还是很困难的。本文主要研究并确定了线性交叉四角链和交叉四角柱状链两类图的拉普拉斯谱，更简便地得到了这两类图的基尔霍夫指标及其生成树数目表达式。另外，还利用交叉四角柱状链的拉普拉斯谱，推导出交叉四角柱状链的度-基尔霍夫指标的表达式。

1 预备知识

本文考虑的均为连通无向图，即图中任意两个顶点都存在路径使其连通。设图G=（V，E），V＝｛1，2，…，n｝和E＝｛e1，e2，…，em｝分别为图G 的顶点集和边集。 di表示顶点i 的度，i＝1，2，…，n。文中未加说明的符号以及定义等参见文献[16]。

定义1.1 图的拉普拉斯矩阵是指由顶点集V作为行和列进行索引n×n 的矩阵，记为L（G）=（lij），其中

定义1.2 拉普拉斯矩阵L（G）的所有特征值称为图G 的拉普拉斯谱；若L（G）的特征值为λ1≥λ2≥…≥λn-1＞λn=0，那么图G 的拉普拉斯谱可记为S（G）=（λ1，λ2，…，λn）。

定义1.3 设H1＝（V1，E1），H2＝（V2，E2）是两个顶点集不相交的简单图，对顶点集V＝V1×V2（即V1与V2的卡氏积）中的任意两个点u=（ui，vj）和v=（up，vq），当ui与up相邻或者ui=up且vj与vq相邻时就将u 和v 连一条边所得到的图。称之为H1与H2的合成图，记为H=H1[H2]。

定义1.4 图G 的一个生成子图若是一棵树，称为图G 的一棵生成树。

定义1.5 将图G 看成一个电网络N 且图G的每条边等价于一个单位电阻，然后计算出电网络N 中任意两个顶点i 与j 之间的有效电阻，即顶点i与j 之间的电阻距离，记为rij[3]。

Hou 等[19]得到了任意两个图的合成图的拉普拉斯特征值和生成树数目的表达式，其中结构相同而标号不同的生成树视为不同的生成树。

引理1.9 设H=H1[H2]，其中｜V（H1）｜＝s，｜V（H2）｜＝t，若S（H1）=（0，μ1，…，μs-1），S（H2）=（0，ω1，…，ωt-1）,图H1的度序列记为d（H1）=（d1，d2，…，ds），那么H=H1[H2]的拉普拉斯特征值是0，tμi（i=1，…，s-1），tdl+ωj（l=1，…，s；j=1，…，t-1）[19]。

引理1.10 设H=H1[H2]，那么的生成树数目τ（H1[H2]）的值为[19]