一类边替换图的平均拉普拉斯多项式

阙林凤，陈海燕

(集美大学理学院，福建 厦门 361021)

设G=(V(G),E(G))是n个顶点，m条边的一个简单图，σ:E(G)→{+1,-1}是定义在G的边集E(G) 上的映射，Gσ=(G,σ)称为符号图，G称为它的基础图，σ是它的符号函数.对给定的一个符号图Gσ，它的邻接矩阵A(Gσ)=(aij)n×n定义如下：

符号图Gσ的拉普拉斯矩阵L(Gσ)=D(G)-A(Gσ);这里D(G)=[d(v1),…，d(vn)]是G的顶点度对角矩阵.

图G的一个边子集M⊆E(G)称为图G的一个匹配，如果G中任意一个顶点最多关联M中的一条边.令M表示图G的所有匹配的集合，则图G的匹配多项式定义为[1]:

早在1978年，Godsil等[2]就证明了如下优美关系式：

这里∑(G)表示E(G)上所有符号函数的集合.关于匹配多项式的更多结果可参见文献[3-4].受上面关系式的启发，2020年，Zhang等[5]定义了一个新的图多项式——平均拉普拉斯多项式：

2020年，Mohammadian[6]定义了直接类比匹配多项式——图的拉普拉斯匹配多项式：

设G和T是两个简单图，i和j是T中两个固定顶点，满足T-i和T-j同构，这里T-i表示由图T去掉顶点i及其所关联的边所得到的图.由G和T按下面的方法构造一个新的图，称为边替换图，记为G[T]:把G的每条边e=(u,v)替换成T,使得i=u,j=v.

由G[T]定义，当T=P3是3个顶点的路，i和j是P3的两个端点时，G[P3]就是G的剖分图，记为S(G),即在G的每条边插入一个新的顶点所得到的图；当T=C3是3个顶点的圈，i和j是它的任意两个顶点时，G[C3]就是G的三角扩展图R(G),这两类变换图的各种性质得到了广泛的研究[7-9].

设G是一个正则图，本文将首先研究边替换图G[T] 和图G的平均拉普拉斯多项式之间的一般关系式.然后在此基础上，研究图G的剖分图、三角扩展图的平均拉普拉斯多项式和图G的平均拉普拉斯多项式之间的关系式，从而得到更具体的结果.

1 边替换图G[T]的平均拉普拉斯多项式

这部分将讨论一般边替换图G[T]的平均拉普拉斯多项式，首先引进一些记号并给出几个引理.

设G是n个顶点的简单图，令m(G,k)表示G的k边匹配的个数，G的匹配生成函数

由匹配多项式的定义，很显然

且有如下关系：

M(G,t)=tng(G,-t-2)；

(1)

引理1[5]设G是n个顶点，m条边的简单图，S(G) 是G的剖分图，则

引理2[5]设G是n个顶点、m条边的d-正则图，则

AT(t)=g(T-i-j,t),

注意到，当T-i和T-j同构时，CT(t)=DT(t).最近，Xin等[10]利用边生成函数得到了边替换图G[T]和G的匹配生成函数之间如下的关系式.

引理3[10]设G是n个顶点、m条边的d-正则图，T是简单图，i和j是T中两个固定顶点(i≠j),且T-i和T-j同构，则G[T]的匹配生成函数

现在给出关于边替换图G[T]的平均拉普拉斯多项式的结果.

定理1设G是n个顶点、m条边的d-正则图，T是n1个顶点、m1条边的简单图，i和j是T中两个固定顶点(i≠j),且T-i和T-j同构，则G[T]的平均拉普拉斯多项式

这里S(T)是T的剖分图，

证明首先由边替换图G[T]的定义和剖分图的定义，可得G[T]有n+(n1-2)m个顶点、mm1条边；S(G[T])=G[S(T)]有n+(n1+m1-2)m个顶点.因此由引理1和式(1)得

tn+(n1-m1-2)mM(G[S(T)],t)=

tn+(n1-m1-2)mtn+(n1+m1-2)mg(G[S(T)],-t-2)=

t2(n+(n1-2)m)g(G[S(T)],-t-2)，

即

(2)

再由引理2、引理3和式(1)得

把上面的结果和式(2)结合在一起，就得到

结论得证.

下一部分将把上面的结果应用到剖分图S(G)和三角扩展图R(G)中，从而得到更具体的结果.

2 剖分图和三角扩展图的平均拉普拉斯多项式

设G是一个简单图，S(G)和R(G)分别表示它的剖分图和三角扩展图，这一部分讨论剖分图S(G)和三角扩展图R(G)的平均拉普拉斯多项式.

定理2设G是n个顶点、m条边的d-正则图，S(G)是它的剖分图，则

证明由定义，S(G)=G[P3],i和j是P3的两个端点，因此很容易得到

AS(P3)(t)=AP5(t)=1+2t,

BS(P3)(t)=BP5(t)=t2,

CS(P3)(t)=CP5(t)=t+t2.

故

(2+d)t+2d).

结论得证.

在文献[5-6]中已证明任意图的平均拉普拉斯多项式的根都是非负实数，因此由定理2可以得到下面的推论.

和一个m-n重根2.

定理3设G是n个顶点、m条边的d-正则图，R(G)是它的三角扩展图，则

证明由定义，R(G)=G[C3],S(C3)=C6.注意到i和j是C3的任意两点，对应C6中距离为2的两个顶点.因此经过计算得

AS(C3)(t)=AC6(t)=1+2t,

BS(C3)(t)=BC6(t)=3t2+2t3，

CS(C3)(t)=CC6(t)=2t+3t2，

进一步可得

故

结论得证.