單圈圖依次小Q－特征值排序

周 敏， 何常香

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

設(shè)G＝（V，E）是有n個(gè)頂點(diǎn)的簡單連通圖（不含環(huán)和多重邊）.其中V＝｛v1，v2，…，vn｝是點(diǎn)集合，E＝｛e1，e2，…，em｝是邊集合.圖G的鄰接矩陣定義為一個(gè)n×n矩陣A（G）＝（aij），其中當(dāng)vi和vj相鄰時(shí)，aij＝1；當(dāng)vi和vj不相鄰時(shí)，aij＝0.假如G是一個(gè)簡單圖，則A（G）是一個(gè)實(shí)對(duì)稱的（0，1）－矩陣且它的主對(duì)角線上的元素全為0.

令d（vi）表示頂點(diǎn)vi的度，圖G的無符號(hào)拉普拉斯矩陣定義為Q（G）＝D（G）＋A（G），其中D（G）是以G的所有頂點(diǎn)的度為對(duì)角元的對(duì)角陣.近年來，特別是文獻(xiàn)［1］發(fā)表之后，關(guān)于無符號(hào)拉普拉斯矩陣的研究日益受到人們的關(guān)注.眾所周知Q（G）是一個(gè)實(shí)對(duì)稱的半正定矩陣，設(shè)其特征值為

qn（G）＝0當(dāng)且僅當(dāng)G有一個(gè)連通分支是二部圖.對(duì)于圖的無符號(hào)拉普拉斯最大特征值已經(jīng)有了深入研究［2－5］，而對(duì)于圖的無符號(hào)拉普拉斯最小特征值的研究相對(duì)較少，文獻(xiàn)［6－8］給出了無符號(hào)拉普拉斯最小特征值的一些結(jié)論.

為方便起見，記圖G的依次小Q－特征值為k（G）.顯然，若G為二部圖，則k（G）＝α（G），其中α（G）為G的代數(shù)連通度.關(guān)于最簡單的連通圖樹的代數(shù)連通度已經(jīng)有了很多結(jié)果［9－12］.本文主要研究單圈圖（邊數(shù)等于頂點(diǎn)數(shù)的連通圖）的k（G）.記階數(shù)為n的所有連通的單圈圖的集合為U（n）.給出了當(dāng)階數(shù)n≥25時(shí)，U（n）中依次小Q－特征值為前3大的圖.下面給出一些必要的定義.

定義1n階圖G叫做單圈圖，如果G是連通的，并且G的邊數(shù)也是n.

定義2 設(shè)G是一個(gè)單圈圖，v是G圈上的點(diǎn)，如果d（v）≥3，則稱v是G的一個(gè)分叉點(diǎn).并記G的分叉點(diǎn)個(gè)數(shù)為Fork（G）.

定義3 設(shè)G是一個(gè)連通圖，uv∈E（G），剖分邊uv，即去掉邊uv，同時(shí)增加一個(gè)新點(diǎn)w以及兩條新邊wu，wv.

對(duì)于整數(shù)n≥3，Cn表示有n個(gè)頂點(diǎn)的圈；Pn表示有n個(gè)頂點(diǎn)的路；Um（n）表示圈長為m≥3的n階單圈圖的全體所構(gòu)成的集合；S（m，n）表示在星 圖K1，m和K1，n的中心添加一條邊所得的圖；S＊（m，n）表示由根點(diǎn)長出m條長為2的懸掛路，n條懸掛邊所得的有根樹.

定義4 設(shè)Us（T1，T2，…，Ts）表示由圈v1v2…vsv1從它上面的點(diǎn)vi分別長出樹Ti（1≤i≤s）（Ti是以vi為根點(diǎn)的有根樹）所得的單圈圖.以根點(diǎn)vi為端點(diǎn)的Ti最長路的長度稱為有根樹Ti的高.當(dāng)Ti為S（m，n）（m≠1）且根點(diǎn)為星圖K1，m的中心時(shí)，簡記Ti為S（m，n）；當(dāng)Ti為K1，m且根點(diǎn)為K1，m的中心時(shí)，簡記Ti為m；若單圈圖Us（T1，T2，…，Ts）中，Ti＋1，…，Ts的高均為0，將其簡記為Us（T1，T2，…，Ti）.

定義5 設(shè)G＝G1u：vG2是由兩個(gè)頂點(diǎn)不相交的連通圖G1和G2通過連接G1中的點(diǎn)u和G2中的點(diǎn)v得到的圖，則G叫做G1，G2關(guān)于點(diǎn)u，v的連通和.

定義6 對(duì)任意圖G和v∈V（G），用Qv（G）表示由G的無符號(hào)拉普拉斯矩陣Q（G）去掉v對(duì)應(yīng)的行和列后得到的主子陣.

對(duì)于只有非負(fù)根的方程P（x）＝0，記τ（P）為它的最小正根.若M是實(shí)對(duì)稱陣，它的最小特征值也記為τ（M）.特別的，記Qv（P3）（其中v為P3的一個(gè)端點(diǎn)）的特征多項(xiàng)式x2－3x＋1為a（x），易得τ（a）≈0.382 00，記為τ0.

表1中列出的是一些在本文證明中用到的k（G）小于τ0的單圈圖及其k（G）.

引理1［8］設(shè)G是一個(gè)n階連通圖，1≤k≤n＋1是一個(gè)自然數(shù)，H由G增加一個(gè)點(diǎn)u，并將u與G中1≤t＜k個(gè)點(diǎn)相連得到的圖，則qk（H）≤qk－t（G）.

表1 k（G）＜τ0的單圈圖及其k（G）Tab.1 Unicycle graph when k（G）＜τ0and its k（G）

引理2［13］設(shè)A＝B＋C，A，B，C均為n階實(shí)對(duì)稱陣，若C恰有t個(gè)正特征值，則有λk（B）≥λk＋t（A）（其中1≤k≤n－t）.

推論1 設(shè)圖G是一個(gè)連通圖，H由G增加一個(gè)懸掛點(diǎn)所得的圖，則k（H）≤k（G）.

證明 設(shè)G的階數(shù)為n，在引理1中取t＝1，k＝n，則qn（H）≤qn－1（G），即k（H）≤k（G）.

推論2 若H是單圈圖，G是H的單圈子圖，則k（H）≤k（G）.

證明 反復(fù)利用推論1即可得此結(jié)論.

引理3［14］設(shè)G是一個(gè)連通圖，G′是由G將其一邊連續(xù)剖分兩次得到的圖，則k（G′）≤k（G）.

結(jié)合推論1和引理3可得如下結(jié)果：

推論3 若圖H去掉某懸掛邊后可以得到G的某種偶次剖分，則k（H）≤k（G）.

引理4［15］設(shè)n階圖G是由圖H從點(diǎn)ν長出t條新懸掛邊得到的圖，則ψ（G）＝ （x－1）t ψ（H）－tx（x－1）t－1ψ（Qv（H））

引理5［16］設(shè)A是一個(gè)n階的Hermitian矩陣且具有特征值λ1≥λ2≥…≥λn.設(shè)B是A的一個(gè)m階主子陣，具有特征值μ1≥μ2≥…≥μm，則λn－m＋i≤μi≤λi（i＝1，2，…，m）.

1 等于τ0的單圈圖

記由n階單圈圖U3（S＊（s，t）），U3（1，S＊（s，t）），U3（1，1，S＊（s，t）），U4（S＊（s，t）），U4（1，S＊（s，t）），U5（S＊（s，t）），U5（n－5），U3（1，1，n－5）（s≥1）組成的圖類為C1類圖（見圖1）.

圖1 C1類Fig.1 C1class

定理1 a.當(dāng)s≥2時(shí)，U3（S＊（s，t）），U3（1，S＊（s，t）），U4（S＊（s，t））的 依 次 小Q－ 特 征 值 等于τ0.

b.當(dāng)s≥1 時(shí)，U3（1，1，S＊（s，t）），U4（1，S＊（s，t）），U5（S＊（s，t））的 依 次 小Q－ 特 征 值 等于τ0.

c.當(dāng)s≥1時(shí)，U5（n－5）的依次小Q－特征值等于τ0.

d.當(dāng)s≥5時(shí)，U3（1，1，n－5）的依次小Q－特征值等于τ0.

證明a.令v是U3（S＊（s，t））唯一的分叉點(diǎn)，則Qv（U3（S＊（s，t）））是s個(gè)Qv（P3），t個(gè)Qv（P2）和一個(gè)Qv（C3）的直和.經(jīng)計(jì)算

故τ0＝τ（Qv（U3（S＊（s，t））））且重?cái)?shù)是s，所以由引理5知當(dāng)s≥2時(shí)，k（U3（S＊（s，t）））＝τ0.

同理可證U3（1，S＊（s，t）），U4（S＊（s，t））的依次小Q－特征值等于τ0.

b.令v是U3（1，1，S＊（s，t））中長出s條長為2的懸掛路的分叉點(diǎn)，則Qv（U3（1，1，S＊（s，t）））是s個(gè)Qv（P3），t個(gè)Qv（P2）和一個(gè)Qv（U3（1，1））的直和，v是P3的端點(diǎn)，同時(shí)也是U3（1，1）中的一個(gè)圈上的非分叉點(diǎn).經(jīng)計(jì)算

故τ0＝τ（Qv（U3（1，1，S＊（s，t））））且重?cái)?shù)是s＋1，所以由引理5知當(dāng)s≥1時(shí)，k（U3（1，1，S＊（s，t）））＝τ0.

同理可證U4（1，S＊（s，t）），U5（S＊（s，t））的依次小Q－特征值等于τ0.

c.當(dāng)s≥1時(shí)

f（τ0）＜0，f（x）是 4 次的，則τ0＞τ（f）.f（－∞）＝＋∞，f（1）＜0，f（3）＞0，f（4）＜0，f（＋∞）＝＋∞.則f（x）在（－∞，1），（1，3），（3，4），（4，＋∞）上有根.所以f（x）的第二小根是大于τ0的，從而τ0是U5（n－5）的依次小Q－特征值.

d.當(dāng)s≥5時(shí)

f（－∞）＝＋∞，f（τ0）＜0，f（1）＞0，f（5）＜0，f（＋∞）＝＋∞.所以f（x）的第二小值是大于τ0的，從而τ0是U3（1，1，n－5）的依次小Q－特征值.

2 k（G）小于τ0的單圈圖

記由n階單圈圖G1＝U3（n－3），G2＝U4（n－4），G3＝U3（1，n－4），G4＝U4（1，n－5），G5＝U3（S＊（1，n－5）），G6＝U4（S＊（1，n－6）），G7＝U3（1，S＊（1，n－6））組成的圖類為C2類圖（見圖2）.

圖2 C2類Fig.2 C2class

任何一個(gè)單圈圖G，若它含有表1中列舉的任一圖的偶次剖分作為單圈子圖，由推論3知k（G）＜τ0.所以證明階數(shù)n≥25的非C1，C2類單圈圖必以表1列舉的某一圖或其偶次剖分作為單圈子圖.在引理6～8中，將按照單圈圖的分叉樹的最大高度來討論.

引理6 設(shè)n階單圈圖G的分叉樹均是以中心為根的星圖（即分叉樹的最大高度為1），若n≥25且G不為C2類圖，則k（G）＜τ0.

證明 證明G以表1中的某個(gè)圖（設(shè)為G0）或其偶次剖分圖為單圈子圖，則k（G）≤k（G0）＜τ0.設(shè)單圈圖的圈長為l.

情形1l≥11

若l為奇數(shù)，則必以C11或其偶次剖分為單圈子圖.若l為偶數(shù)，則必以C12或其偶次剖分為單圈子圖.

情形2l＝10

由于n≥25，G必以U10（1）為單圈子圖.

情形3l＝9

G必以U9（1）為單圈子圖.

情形4l≤8

子情形al＝8.由n≥25知，G必以U8（2）為單圈子圖.

子情形bl＝7.由n≥25知，G必以U7（3），U7（2，0，2）之一為單圈子圖.

子情形cl＝6

若G中有階數(shù)大于6的分叉樹，則G必以U6（6）為單圈子圖.若G中分叉樹的階數(shù)均小于等于6，由n≥25知G至少以U4（2，0，4），U4（4，4）之一的偶次剖分為單圈子圖.由于G的分叉樹均是以中心為根的星圖，且G不是G1，G2，U5（n－5），故當(dāng)圈長l≤5時(shí)，只需考慮分叉點(diǎn)數(shù)Fork（G）≥2的情形.

子情形dl＝5

若G中有階數(shù)大于10的分叉樹，則G至少以U5（1，11），U5（3，4），U5（1，0，5）之一為單圈子圖.若G中分叉樹的階數(shù)均小于等于10，由n≥25知G至少以U5（3，4），U5（2，0，3），U5（1，0，5）之一為單圈子圖.

子情形el＝4

子情形（a）Fork（G）＝2

首先考慮G中有一個(gè)2階分叉樹的情況.由于G不是G4，故G的這兩個(gè)分叉點(diǎn)不相鄰，由n≥25可知G必以U4（1，0，12）為單圈子圖.當(dāng)G中分叉樹的階數(shù)都大于2時(shí)，由n≥25知G至少以U4（2，8），U4（2，0，4），U4（4，4）之一為單圈子圖.

子情形（b）Fork（G）＝3

若G中恰有一個(gè)分叉樹階數(shù)大于2，由n≥25可知G至少以U4（1，1，7），U4（1，17，1）之一為單圈子圖.若G中有兩個(gè)分叉樹階數(shù)都大于2，G至少以U4（2，8），U4（2，0，4），U4（4，4）之一為單圈子圖.

子情形（c）Fork（G）＝4

若G中恰有一個(gè)階數(shù)大于2的分叉樹，G必以U4（1，1，1，6）為單圈子圖.若G中有兩個(gè)階數(shù)大于2的分叉樹，由n≥25可知G至少以U4（2，8），U4（2，0，4），U4（4，4）之一為單圈子圖.

子情形fl＝3

子情形（a）Fork（G）＝2

由于G不是G3，故G中的兩個(gè)分叉樹的階數(shù)都大于2，由n≥25可知G至少以U3（2，20），U3（3，7），U3（4，5）之一為單圈子圖.

子情形（b）Fork（G）＝3

由于G不是U3（1，1，n－5），故G中有兩個(gè)階數(shù)大于2的分叉樹，由n≥25可知G至少以U3（3，7），U3（4，5），U3（1，2，12），U3（2，2，8）之 一 為單圈子圖.

引理7 設(shè)G為n≥19階單圈圖，若G的所有分叉樹的最大高度為2，且G不為C1，C2類圖，則k（G）＜τ0.

證明 思路與定理1一樣.

情形1l≥11

若l為奇數(shù)，則必以C11或其偶次剖分為單圈子圖.若l為偶數(shù)，則必以C12或其偶次剖分為單圈子圖.

情形2l＝10

由于n≥25，G必以U10（1）為單圈子圖.

情形3l＝9

G必以U9（1）為單圈子圖.

情形4l≤8

當(dāng)G中至少有兩個(gè)分叉樹的高為2時(shí)，G至少以U3（P3，P3，1），U3（P3，S＊（1，1）），U4（P3，P3），U4（P3，0，P3）之一的偶次剖分為單圈子圖.

當(dāng)G中只有一個(gè)分叉樹的高為2時(shí)，若此分叉樹有頂點(diǎn)（除根點(diǎn)外）度數(shù)大于2，由n＞17，G必以U3（2，P3），U4（S（0，2））之一的偶次剖分為單圈子圖.所以，假設(shè)G中只有一個(gè)分叉樹的高度為2，且分叉樹上的點(diǎn)（除根點(diǎn)和懸掛點(diǎn)外）均為2度點(diǎn).設(shè)l為G中圈的長度.

子情形al＝3

若Fork（G）＝2，即G某個(gè)U3（r，S＊（s，t）），由于G不是G7，故r＞1，從而G必以U3（2，P3）為單圈子圖.

若Fork（G）＝3，即G為某個(gè)U3（q，r，S＊（s，t）），由于G不是U3（1，1，S＊（s，t）），所以q，r中必有一個(gè)大于1，進(jìn)而有G以U3（2，P3）為單圈子圖.

子情形bl＝4若Fork（G）＝2，若G的兩個(gè)分叉點(diǎn)相鄰，由于G不是U4（1，S＊（s，t）），G必以U4（2，P3）為單圈子圖；若G的兩個(gè)分叉點(diǎn)不相鄰，G必以U4（1，0，P3）為單圈子圖.若Fork（G）＞2，則G也必以U4（1，0，P3）為單圈子圖.

子情形cl＝5

Fork（G）≥2，則G以U3（2，P3）的偶次剖分或U5（S＊（1，1），1）為單圈子圖.

子情形dl＝6

G至少含U6（P3）或U4（1，0，P3）的偶次剖分為單圈子圖.

子情形el＝7

G至少含U5（1，P3）或U5（1，0，P3）的偶次剖分之一為單圈子圖.

子情形fl＝8

G必含U6（P3）的偶次剖分為單圈子圖.

引理8G為n階單圈圖，若G分叉樹的最大高度大于2，則k（G）＜τ0.

證明 此時(shí)G至少含U4（P4），U7（P4）（的偶次剖分）之一為單圈子圖.

當(dāng)l＝3時(shí)，G必含U3（P3，P4）為單圈子圖.

當(dāng)l＝5時(shí)，G必含U5（P3，P4）為單圈子圖.

由引理6～8可得：

定理2 當(dāng)n≥25時(shí)，所有不是C1，C2類的n階單圈圖的依次小Q－特征值均小于τ0.

3 k（G）大于τ0的單圈圖

定理3 當(dāng)n≥25時(shí)

k（G1），k（G2），k（G3），k（G4），k（G5），k（G6），k（G7）都是大于τ0的.

首先由引理4可知Gi（i＝1，…7）的無符號(hào)拉普拉斯特征多項(xiàng)式為

證明 首先證明k（G1）＞τ0，f1（x）＝x3－（n＋3）x2＋3nx－4，對(duì)f1（x）求導(dǎo)，f1′（x）＝3x2－2（n＋3）x＋3n，當(dāng)x＜1時(shí)，f′1（x）＞0，則f1（x）在（－∞，1）上是單調(diào)遞增的，又f1（－∞）＝－∞，f1（1）＝2n－6＞0，所以f1（x）＝0在（－∞，1）恰有一根，故k（G1）＝1＞τ0.

再證k（G2）＞τ0.

f2（x）＝（x2－3x＋1）（x－n）＋（n－3）x－n.當(dāng)x＜τ0時(shí)，x2－3x＋1＞0，x－n＜0，（n－3）x－n＜0.所以f2（x）＜0，則τ（f2）＞τ0.綜上k（G2）＞τ0.k（G4）＞τ0，k（G6）＞τ0同理可證.

下證k（G3）＞τ0.

經(jīng)計(jì)算f3（x）＝f2（x）（x2－2x－1）－6x2＋（3n＋6）x－4－2n，f3（－∞）＝－∞，f3（τ0）＞0，f3（1）＜0，f3（2）＞0，f3（4）＜0，f3（25）＞0.顯然k（G3）＞τ0.

k（G5）＞τ0，k（G7）＞τ0同理可證.

4 主要結(jié)果

設(shè)C1，C2類圖分別如圖1和圖2所示，由定理1、定理2和定理3可得本文的主要結(jié)論.

定理4 如果G是一個(gè)n≥25階單圈圖，則

a.k（G）＝，當(dāng)且僅當(dāng)G是C1類圖.

b.k當(dāng)且僅當(dāng)G是C2類圖.

c.k當(dāng)且僅當(dāng)G既不是C1類，也不是C2類的單圈圖.

［1］CvetkovicˇD M.Signless Laplacian and line graph［M］.Berlin：Mathematiques Naturelles，2005.

［2］Wang J F，Huang Q X，F(xiàn)rancesco B.On graph whose signless Laplacian index does not exceed 4.5［J］.Linear Algebra and Its Applications，2009，431（1）：162－178.

［3］Kinkar C D.On conjectues involving second largest signless Laplacian eigenvalue of graphs［J］.Linear Algebra and Its Applications，2010，432（11）：3018－3029.

［4］Wang J F，F(xiàn)rancesco B，Huang Qiongxiang.On the two largesr Q－eigenvalues of graphs［J］.Discrete Mathematics，2010，310（21）：2858－2866.

［5］Chen Y Q，Wang L G.Sharp bounds for the largest eigenvalue of the signless Laplacian of a graph［J］.Linear Algebra and Its Applications，2010，433（5）：908－913.

［6］Leonardo S L，Carla S，Nair M A.The smallest eigenvalue of the signless Laplacian ［J］.Linear Algebra and Its Applications，2011，436（10）：2570－2584.

［7］Cardoso D M，Cvetkovic D，Rowlinson P.A sharp lower bound for the least eigenvalue of the signless Laplacian of a non－bipartite graph［J］.Linear Algebra and Its Applications，2008，429（12）：2770－2780.

［8］He C X，Zhou M.The least Q－eigenvalue of graph［J］.Journal of East China Normal University，2012，163（3）：1－5.

［9］Liu Y.The ordering of limit point of algebraic connectivity of trees［J］.Journal of Natural Science of Heilongjiang University，2008，25（1）：103－106.

［10］Gu L，Yuan W G，Zhang X D.Algebraic connectivity of trees with the maximum degree［J］.Journal of East China Normal University，2011，163（3）：29－34.

［11］Liu Y，Shao J Y，Yuan X Y.The ordering of trees with perfect matching by the algebraic connectivity［J］.Advanced in Mathematics，2008，37（3）：270－282.

［12］Fan Y Z.A new proof of Fiedler’s inequality on the Algebraic connectivity of trees ［J］.Journal of Mathematical Study，2003，36（4）：289－383.

［13］Grone R，Merris R.The Laplacian spectrum of a graph［J］.SIAMJ Matrix Analytics and Apply，1990，11（2）：218－238.

［14］He C X，Hao P.The smallest signless Laplacian eigenvalue of graphs under perturbation［J］.ELA，2012，310（23）：473－482.

［15］CvetkovicD M，Doob M，Sachs H.Spectra of graphs［M］.New York：Academic Press，1980.

［16］CvetkovicD M，Doob M，Sachs H.Spectra of graphstheory and application ［M］.Heidelberg：Johann Ambrosius Barth Verlag，1995.