一類邊替換圖的平均拉普拉斯多項(xiàng)式

闕林鳳，陳海燕

(集美大學(xué)理學(xué)院，福建 廈門 361021)

設(shè)G=(V(G),E(G))是n個(gè)頂點(diǎn)，m條邊的一個(gè)簡(jiǎn)單圖，σ:E(G)→{+1,-1}是定義在G的邊集E(G) 上的映射，Gσ=(G,σ)稱為符號(hào)圖，G稱為它的基礎(chǔ)圖，σ是它的符號(hào)函數(shù).對(duì)給定的一個(gè)符號(hào)圖Gσ，它的鄰接矩陣A(Gσ)=(aij)n×n定義如下：

符號(hào)圖Gσ的拉普拉斯矩陣L(Gσ)=D(G)-A(Gσ);這里D(G)=[d(v1),…，d(vn)]是G的頂點(diǎn)度對(duì)角矩陣.

圖G的一個(gè)邊子集M?E(G)稱為圖G的一個(gè)匹配，如果G中任意一個(gè)頂點(diǎn)最多關(guān)聯(lián)M中的一條邊.令M表示圖G的所有匹配的集合，則圖G的匹配多項(xiàng)式定義為[1]:

早在1978年，Godsil等[2]就證明了如下優(yōu)美關(guān)系式：

這里∑(G)表示E(G)上所有符號(hào)函數(shù)的集合.關(guān)于匹配多項(xiàng)式的更多結(jié)果可參見文獻(xiàn)[3-4].受上面關(guān)系式的啟發(fā)，2020年，Zhang等[5]定義了一個(gè)新的圖多項(xiàng)式——平均拉普拉斯多項(xiàng)式：

2020年，Mohammadian[6]定義了直接類比匹配多項(xiàng)式——圖的拉普拉斯匹配多項(xiàng)式：

設(shè)G和T是兩個(gè)簡(jiǎn)單圖，i和j是T中兩個(gè)固定頂點(diǎn)，滿足T-i和T-j同構(gòu)，這里T-i表示由圖T去掉頂點(diǎn)i及其所關(guān)聯(lián)的邊所得到的圖.由G和T按下面的方法構(gòu)造一個(gè)新的圖，稱為邊替換圖，記為G[T]:把G的每條邊e=(u,v)替換成T,使得i=u,j=v.

由G[T]定義，當(dāng)T=P3是3個(gè)頂點(diǎn)的路，i和j是P3的兩個(gè)端點(diǎn)時(shí)，G[P3]就是G的剖分圖，記為S(G),即在G的每條邊插入一個(gè)新的頂點(diǎn)所得到的圖；當(dāng)T=C3是3個(gè)頂點(diǎn)的圈，i和j是它的任意兩個(gè)頂點(diǎn)時(shí)，G[C3]就是G的三角擴(kuò)展圖R(G),這兩類變換圖的各種性質(zhì)得到了廣泛的研究[7-9].

設(shè)G是一個(gè)正則圖，本文將首先研究邊替換圖G[T] 和圖G的平均拉普拉斯多項(xiàng)式之間的一般關(guān)系式.然后在此基礎(chǔ)上，研究圖G的剖分圖、三角擴(kuò)展圖的平均拉普拉斯多項(xiàng)式和圖G的平均拉普拉斯多項(xiàng)式之間的關(guān)系式，從而得到更具體的結(jié)果.

1 邊替換圖G[T]的平均拉普拉斯多項(xiàng)式

這部分將討論一般邊替換圖G[T]的平均拉普拉斯多項(xiàng)式，首先引進(jìn)一些記號(hào)并給出幾個(gè)引理.

設(shè)G是n個(gè)頂點(diǎn)的簡(jiǎn)單圖，令m(G,k)表示G的k邊匹配的個(gè)數(shù)，G的匹配生成函數(shù)

由匹配多項(xiàng)式的定義，很顯然

且有如下關(guān)系：

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

(1)

引理1[5]設(shè)G是n個(gè)頂點(diǎn)，m條邊的簡(jiǎn)單圖，S(G) 是G的剖分圖，則

引理2[5]設(shè)G是n個(gè)頂點(diǎn)、m條邊的d-正則圖，則

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

注意到，當(dāng)T-i和T-j同構(gòu)時(shí)，CT(t)=DT(t).最近，Xin等[10]利用邊生成函數(shù)得到了邊替換圖G[T]和G的匹配生成函數(shù)之間如下的關(guān)系式.

引理3[10]設(shè)G是n個(gè)頂點(diǎn)、m條邊的d-正則圖，T是簡(jiǎn)單圖，i和j是T中兩個(gè)固定頂點(diǎn)(i≠j),且T-i和T-j同構(gòu)，則G[T]的匹配生成函數(shù)

現(xiàn)在給出關(guān)于邊替換圖G[T]的平均拉普拉斯多項(xiàng)式的結(jié)果.

定理1設(shè)G是n個(gè)頂點(diǎn)、m條邊的d-正則圖，T是n1個(gè)頂點(diǎn)、m1條邊的簡(jiǎn)單圖，i和j是T中兩個(gè)固定頂點(diǎn)(i≠j),且T-i和T-j同構(gòu)，則G[T]的平均拉普拉斯多項(xiàng)式

這里S(T)是T的剖分圖，

證明首先由邊替換圖G[T]的定義和剖分圖的定義，可得G[T]有n+(n1-2)m個(gè)頂點(diǎn)、mm1條邊；S(G[T])=G[S(T)]有n+(n1+m1-2)m個(gè)頂點(diǎn).因此由引理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)得

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

結(jié)論得證.

下一部分將把上面的結(jié)果應(yīng)用到剖分圖S(G)和三角擴(kuò)展圖R(G)中，從而得到更具體的結(jié)果.

2 剖分圖和三角擴(kuò)展圖的平均拉普拉斯多項(xiàng)式

設(shè)G是一個(gè)簡(jiǎn)單圖，S(G)和R(G)分別表示它的剖分圖和三角擴(kuò)展圖，這一部分討論剖分圖S(G)和三角擴(kuò)展圖R(G)的平均拉普拉斯多項(xiàng)式.

定理2設(shè)G是n個(gè)頂點(diǎn)、m條邊的d-正則圖，S(G)是它的剖分圖，則

證明由定義，S(G)=G[P3],i和j是P3的兩個(gè)端點(diǎn)，因此很容易得到

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

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

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

故

(2+d)t+2d).

結(jié)論得證.

在文獻(xiàn)[5-6]中已證明任意圖的平均拉普拉斯多項(xiàng)式的根都是非負(fù)實(shí)數(shù)，因此由定理2可以得到下面的推論.

和一個(gè)m-n重根2.

定理3設(shè)G是n個(gè)頂點(diǎn)、m條邊的d-正則圖，R(G)是它的三角擴(kuò)展圖，則

證明由定義，R(G)=G[C3],S(C3)=C6.注意到i和j是C3的任意兩點(diǎn)，對(duì)應(yīng)C6中距離為2的兩個(gè)頂點(diǎn).因此經(jīng)過計(jì)算得

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

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

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

進(jìn)一步可得

故

結(jié)論得證.