雙圈圖的無(wú)符號(hào)拉普拉斯特征多項(xiàng)式的系數(shù)

徐麗珍， 何常香

（上海理工大學(xué) 理學(xué)院，上海 200093）

1 基本定義

式中，I為n 階單位矩陣.

如果連通圖G 的邊數(shù)等于頂點(diǎn)數(shù)，則稱G 為單圈圖；如果連通圖G 的邊數(shù)等于頂點(diǎn)數(shù)加1，則稱G為雙圈圖.G－e表示由G 刪去邊e后得到的圖.

定義1［1］設(shè)H 是圖G 的一個(gè)生成子圖，若H的連通分支是樹，或者是圈長(zhǎng)為奇數(shù)的單圈圖，則稱H 是圖G 的一個(gè)TU－子圖；若H 恰有c個(gè)圈長(zhǎng)為奇數(shù)的單圈分支和s個(gè)樹分支T1，T2，…，Ts，則定義表示樹Ti的階數(shù).

引理1［1］設(shè)Hi為圖G 中所有具有i 條邊的TU－子圖集合，則式（1）中p0（G）＝1，

在引理1中，由于Hi的確定比較困難，所以，pi（G）也很難被確定.文獻(xiàn)［1］給出了無(wú)符號(hào)拉普拉斯特征多項(xiàng)式系數(shù)p1（G）和p2（G）的表達(dá)式.文獻(xiàn)［2］給出了p3（G）的表達(dá)式.文獻(xiàn)［3］給出了經(jīng)刪邊、剖分及移鄰等變換后所得圖G′的pi（G′）的絕對(duì)值與原圖pi（G）的絕對(duì)值的大小關(guān)系，并以此為工具，確定了無(wú)符號(hào)拉普拉斯特征多項(xiàng)式系數(shù)絕對(duì)值最小的單圈圖.更多關(guān)于系數(shù)的研究見文獻(xiàn)［4－9］.現(xiàn)主要研究雙圈圖的無(wú)符號(hào)拉普拉斯特征多項(xiàng)式的常數(shù)項(xiàng).

2 雙圈圖的分類

設(shè)B（n）為所有n 階雙圈圖的集合，不含懸掛點(diǎn)的雙圈圖有B（r，s，l）和B（Pk，Pl，Pt）這兩類，如圖1所示.

易見Bn（n）＝B1（n）∪B2（n）.

圖1 B（r，s，l）和B（Pk，Pl，Pt）Fig.1 B（r，s，l）and B（Pk，Pl，Pt）

3 雙圈圖的無(wú)符號(hào)拉普拉斯系數(shù)pn（G）

現(xiàn)主要給出兩類雙圈圖的無(wú)符號(hào)拉普拉斯特征多項(xiàng)式的常數(shù)項(xiàng).

定義4 設(shè)圖G 是n 階連通圖，e＝v1v2是圖G的一條非懸掛邊，在圖G 中的點(diǎn)v1處添加一條懸掛邊，再將邊e收縮（即將點(diǎn)v1和v2粘合）后得到一個(gè)新的n階連通圖G′＝τ（G，1，2）.

定理1 設(shè)G∈B1（n），則

證明 由引理1可知

若H∈Hn，則H 為G 的邊數(shù)為n＋1－1＝n 的TU－子圖，即存在e∈E（G）使得H ＝G－e；若e?E（），則G－e?Hn.以下假設(shè)e∈E），按r，s的奇偶性進(jìn)行討論.

情形1 若r，s均為偶數(shù).

此時(shí)Hn＝φ，從而有pn（G）＝0.

情形2 若r，s的奇偶性不同.

不失一般性，不妨設(shè)x＝r 為偶數(shù)（即Cr為偶圈）.只有當(dāng)e∈E（Cr）時(shí)，H＝G－e才是G 的TU－子圖，并且此時(shí)的W（H）＝4，從而有

情形3 若r，s均為奇數(shù).

若e不在圈上，則G－e是G 的含2個(gè)奇單圈分支的TU－子圖，故W（H）＝42；若e在圈上，則Ge是G 的恰有1個(gè)奇單圈分支的TU－子圖，且W（H）＝4.綜上

由定理1的結(jié)論可知，收縮加懸掛邊后雙圈圖中圈的奇偶性發(fā)生改變，所以，圖的無(wú)符號(hào)拉普拉斯特征多項(xiàng)式系數(shù)pn（G）的大小關(guān)系很難確定.

例1 設(shè)圖G 的階數(shù)為n＝9，圖G′和G″是由圖G 收縮邊v1v2加一條懸掛邊于點(diǎn)v1而得到的，如圖2和3所示.

圖2 圖G1和圖G′＝τ（G1，1，2）Fig.2 Graph G1and G′＝τ（G1，1，2）

圖3 圖G2和圖G″＝τ（G2，1，2）Fig3 Graph G2and G″＝τ（G2，1，2）

顯然pn（G1）＝pn（G2）＝－16，pn（G′）＝－（4×5＋4×3＋42×1）＝－48，pn（G″）＝0，pn（G1）≥pn（G′），pn（G2）≤pn（G″）.

定理2 設(shè)G∈B2（n），則

式中，x，y 為k，l，t中奇偶性相同的2個(gè)數(shù).

證明 由引理1可知

若H∈Hn，則H 為G 的邊數(shù)為n＋1－1＝n 的TU－子圖，即存在e∈G 使得H ＝G－e；若e?，則G－e?Hn.以下假設(shè)e∈，按k，l，t的奇偶性進(jìn)行討論.

情形1 若k，l，t這三者的奇偶性相同.

不失一般性，不妨假設(shè)k，l，t均為偶數(shù)，此時(shí)Hn＝φ，從而有pn（G）＝0.

情形2 若k，l，t這三者的奇偶性不完全相同.不妨設(shè)x＝l，y＝t為偶數(shù)，k為奇數(shù).

若e在x 到y(tǒng) 的長(zhǎng)為k 的路中，則G－e不是TU－子圖；若e在x 到y(tǒng) 的長(zhǎng)為l或t的路中，則G－e是G 的恰有一個(gè)奇單圈分支的TU－子圖，故W（H）＝4.綜上

由定理1和定理2可知，對(duì)于非二部雙圈圖，pn（G）的絕對(duì)值有最小值16.由定理1和r≥3，s≥3可知，當(dāng)r＝4或s＝4時(shí)，pn（G）的絕對(duì)值取到最小值16，即非二部雙圈圖的pn（G）的絕對(duì)值取到最小值16時(shí)，第一類雙圈圖B1（n）必含有1個(gè)C4圈和1個(gè)奇單圈；由定理2可知，當(dāng)x＝1，y＝3或x＝2，y＝2時(shí)，pn（G）的絕對(duì)值取到最小值16，即非二部圖pn（G）的絕對(duì)值取到最小值16時(shí)，第二類雙圈圖B2（n）必含有1個(gè)C4圈和1個(gè)奇單圈.同時(shí)，由以上定理可知，雙圈圖的無(wú)符號(hào)拉普拉斯特征多項(xiàng)式的常數(shù)項(xiàng)只與圈長(zhǎng)的奇偶性有關(guān).

［1］Cvetkovi D，Rowlinson P，Simic S.Signless Laplacian of finite graphs［J］.Linear Algebra and its Applications，2007，423（1）：155－171.

［2］Wang J F，Huang Q H.Some results on the signless Laplacians of graphs［J］.Applied Mathematics Letters，2010，23（9）：1045－1049.

［3］Mirzakhah M，Kiani D.Some results on signless Laplacian coefficients of graphs［J］.Linear Algebra and its Applications，2012，437（9）：2243－2251.

［4］Oliveira C S，Maia de Abreu N M，Jurkiewicz S.The characteristic polynomial of the Laplacian of graphs in（a，b）－linear classes［J］.Linear Algebra and its Applications，2002，356（1／2／3）：113－121.

［5］He C X，Shan H Y.On the Laplacian coefficients of bicyclic graphs［J］.Discrete Mathematics，2010，310（23）：3404－3412.

［6］Mohar B.On the Laplacian coefficients of acyclic graphs［J］.Linear Algebra and its Applicatons，2007，422（2／3）：736－741.

［7］Ilic A，Ilic M.Laplacian coefficients of trees with given number of leaves or vertices of degree two［J］.Linear Algebra and its Applications，2009，431（11）：2195－2202.

［8］Stevanovic D，Ilic A.On the Laplacian coefcients of unicyclic graphs［J］.Linear Algebra and its Applications，2009，430（8／9）：2290－2300.

［9］陳永玲，何常香.二部雙圈圖的拉普拉斯系數(shù)［J］.上海理工大學(xué)學(xué)報(bào)，2012，34（5）：481－486.