無(wú)符號(hào)拉普拉斯譜半徑與圖的若干性質(zhì)

劉莉 袁慧 何煥

（安慶師范大學(xué) 數(shù)理學(xué)院，安徽 安慶 246133）

0 引言

所考慮的圖均為簡(jiǎn)單無(wú)向圖。設(shè)G=（V，E）是 n 階圖，頂點(diǎn)集 V=V（G） ={v1，v2，…，vn}，邊集E=E（G） ={e1，e2，…，en}為 G 的二元重集構(gòu)成的集合。頂點(diǎn)v的度dG（v）是指G中與v關(guān)聯(lián)的邊數(shù)，G的最小度記作δ。G中vi與vj之間的距離，記作 dG（vi，vj）。設(shè) G= （V，E）是 n 階圖，記 Gc=（V，Ec）為圖 G= （V，E）的補(bǔ)圖，其中 Ec={xy∶x，y∈V，x≠y，xy?E}。設(shè) G=（V（G），E（G）），H= （V（H），E（H））是兩個(gè)圖。若 V（H）?V（G）且 E（H）?E（G），則稱(chēng) H 是 G 的子圖。若 V（H）?V（G）或E（H）?E（G），此時(shí)H就是G的真子圖。特別地，當(dāng) V（H）=V（G）或 E（H）=E（G）時(shí)，我們將 H 和G 視為同一個(gè)圖。若有 V（H）=V（G）且 E（H）?E（G），則H就是G的生成子圖。

因?yàn)猷徑泳仃嘇（G），無(wú)符號(hào)拉普拉斯矩陣Q（G）是實(shí)對(duì)稱(chēng)矩陣，所以它們的特征值是實(shí)數(shù)并可以排序。圖G的無(wú)符號(hào)拉普拉斯譜半徑，是Q（G）的最大特征值 q（G）。

如果圖G至少含有兩個(gè)頂點(diǎn)，且任意刪去小于s條邊后仍然保持連通，則稱(chēng)圖G是s-邊-連通的。如果一個(gè)圖G的點(diǎn)集V（G）可以被s條或者更少條點(diǎn)不交的路覆蓋，那么稱(chēng)圖G是s-路-覆蓋的。如果|X|≤s，X?V（G），由 V（G）-X 得到的導(dǎo)出子圖是哈密爾頓的，那么稱(chēng)圖G是s-哈密爾頓的。如果圖G中任意點(diǎn)不交的路構(gòu)成的集合最多有s條邊同時(shí)在圖G的一個(gè)哈密爾頓圈上，那么稱(chēng)圖G是s-邊-哈密爾頓的。設(shè)S?V，圖G[S]表示以S為頂點(diǎn)集，以圖G中兩端點(diǎn)均在S中的邊為邊集的圖，若圖G[S]中無(wú)邊，則稱(chēng)S為G的獨(dú)立集。圖G的獨(dú)立數(shù)α（G），是圖G中最大獨(dú)立集所含的點(diǎn)數(shù)。

穩(wěn)定性的概念是由Bondy和Chvátal[1]提出的，設(shè)P是n階圖G的一個(gè)性質(zhì)，k為非負(fù)整數(shù)，如果對(duì)任意邊 uv∈E（Gc）且 dG（u）+dG（v）≥k，G+uv具有性質(zhì)P，那么圖G本身具有性質(zhì)P，則稱(chēng)此性質(zhì)P是k-穩(wěn)定的。圖G的k-閉包不僅是唯一確定的，并且所增加的邊與次序無(wú)關(guān)，并且在閉包c(diǎn)lk（G）中，對(duì)于任意的不相鄰的點(diǎn)對(duì) u，v，均有 dclk（G）（u）+dclk（G）（v）≤ k-1。文中沒(méi)有提及的概念請(qǐng)參考文獻(xiàn)[2]。

圖論是一門(mén)古老而又活躍的學(xué)科，涉及面很廣，隨著計(jì)算機(jī)及信息技術(shù)的飛速發(fā)展，離散數(shù)學(xué)起著舉足輕重的作用。圖的哈密爾頓問(wèn)題一直以來(lái)都是圖論方向研究的重點(diǎn)和難點(diǎn)。圖的哈密爾頓問(wèn)題一直是圖論的熱點(diǎn)問(wèn)題，它是NP-完全問(wèn)題，至今還沒(méi)有被完美的解決。圖的譜便于計(jì)算，所以利用圖的譜來(lái)研究圖的哈密爾頓性的文章很多。利用圖的譜來(lái)刻畫(huà)取得了很多成果，有不少學(xué)者做了更深入的研究，并得到了一些較好的結(jié)論。例如周波[3]給出了圖存在哈密爾頓路和哈密爾頓圈的無(wú)符號(hào)拉普拉斯譜充分條件。余桂東等[4]利用補(bǔ)圖的譜半徑刻畫(huà)具有較大最小度的圖是 s-連通、s-邊-連通、s-路-覆蓋、s-哈密爾頓、s-邊-哈密爾頓的充分條件。余桂東等[5]分別利用補(bǔ)圖的譜半徑給出了具有較大最小度的簡(jiǎn)單圖是哈密爾頓-連通的以及從任意點(diǎn)出發(fā)可跡的充分條件，同理原圖也是；周倩楠等[6]研究了具有較大最小度的圖是哈密爾頓-連通的無(wú)符號(hào)拉普拉斯譜充分條件。徐奕等[7]分別借助圖的大小、譜半徑和無(wú)符號(hào)拉普拉斯譜半徑給出了圖是哈密爾頓-連通的一些充分條件。受以上文獻(xiàn)啟發(fā)，本研究在補(bǔ)圖中，利用無(wú)符號(hào)拉普拉斯譜半徑分別給出了具有較大最小度的圖G是s-連通、s-邊-連通、s-路-覆蓋、s-哈密爾頓、s-邊-哈密爾頓、s-哈密爾頓-連通或α（G）≤s的充分條件。

1 預(yù)備知識(shí)

下面介紹本研究中需要用到相關(guān)引理及特殊圖類(lèi)。

引理1.1[2]設(shè)P是圖G的一個(gè)性質(zhì)，如果P是s-穩(wěn)定的，并且cls（G）也具有性質(zhì)P，那么圖G本身也具有性質(zhì)P。

引理1.2[2]

（1）“n 階圖 G 是 s-連通圖”的性質(zhì)是（n+s-2）-穩(wěn)定的。

（2）“n階圖 G 是 s-邊-連通圖”的性質(zhì)是（n+s-2）-穩(wěn)定的。

（3）“n階圖 G 是 s-路-覆蓋圖”的性質(zhì)是（ns）-穩(wěn)定的。

（4）“n階圖 G 是 s-哈密爾頓圖”的性質(zhì)是（n+s）-穩(wěn)定的。

（5）“n階圖 G 是 s-邊-哈密爾頓圖”的性質(zhì)是（n+s）-穩(wěn)定的。

（6）“n階圖 G 是 s-哈密爾頓-連通圖”的性質(zhì)是（n+s+1）-穩(wěn)定的。

（7）“n 階圖 G 滿足 α（G）≤s”的性質(zhì)是（2n-2s-1）-穩(wěn)定的。

引理 1.3[6]設(shè) G是非空?qǐng)D，則。若 G 是連通的，等號(hào)成立當(dāng)且僅當(dāng)G是正則圖或二部半正則圖。

引理 1.4 設(shè)G是n階連通圖，則q（G）≥2λ（G）。等號(hào)成立當(dāng)且僅當(dāng)G是正則圖。

證明 設(shè) X={x1，x2，…，xn}T是 λ（G）所對(duì)應(yīng)的單位特征向量，這里xi對(duì)應(yīng)于頂點(diǎn)vi，則q（G）。

若 G 是 d-正則圖，則 λ（G）=d。又因?yàn)?Q（G）=D（G）+A（G），則 q（G）=2d，即 q（G）=2λ（G）。證明完成。

結(jié)合引理1.3和引理1.4，可得下面的引理。

引理1.6[8]（Perron-Frobenius定理）設(shè)A是n（＞1）階方陣 A（≥0），且是不可約的，記 μ（A）=max{|λ1|，…，|λn|}，這里{λ1，…，λn}是 A 的 n 個(gè)特征值。則有：μ（A）作為 A 的 n2個(gè)元素的函數(shù)，μ（A）是嚴(yán)格遞增的，即若有 B≠A，B-A≥0，則 μ（B）≥μ（A）。

接下來(lái)介紹定理中需要用到的特殊圖類(lèi)：

設(shè)QP是滿足下列條件的n階圖的集合：Fc∨G1，其中 F 是 r（n-k≤r≤n）階的（n-k-1）-正則圖，G1是Kn-r的生成子圖。

2 主要結(jié)果

接下來(lái)從補(bǔ)圖的角度出發(fā)，根據(jù)無(wú)符號(hào)拉普拉斯譜半徑，給出一個(gè)圖具有s-穩(wěn)定的性質(zhì)P的充分條件。

定理2.1 設(shè)G是 n階簡(jiǎn)單圖，s≥1，k≥1，n ≥ 2k+1，δ（G）≥k≥s+1-n，如果，那么圖G具有s-穩(wěn)定的性質(zhì)P，除非G∈QP。

證明 構(gòu)造閉包H∶=cls（G）。假設(shè)G不具有s-穩(wěn)定的性質(zhì)P，根據(jù)引理1.1知H也不具有s-穩(wěn)定的性質(zhì)P。根據(jù)閉包的定義知，H中任意兩個(gè)不相鄰頂點(diǎn) u，v 的度和 dH（u）+dH（v）≤ s-1，即對(duì)Hc中任意一條邊 uv∈E（Hc）都有

又因?yàn)?δ（G）≥k，且 H是 G的閉包，故有dH（u）≥dG（u）≥k，dH（v）≥dG（v）≥k，即有 dHc（u）≤n-k-1，dHc（v）≤n-k-1，結(jié)合式（1）可知

根據(jù)式（2）設(shè) f（x）=x（2n-s-1-x），n-s+k≤ x≤n-k-1。結(jié)合函數(shù) f（x）的圖像得到 f（x）≥（n-s+k）（n-k-1），當(dāng)且僅當(dāng) x=n-s+k 或 x=n-k-1時(shí)等號(hào)成立。因此對(duì)任意邊uv∈E（Hc），，等號(hào)成立當(dāng)且僅當(dāng) dHc（u）=n-s+k，且 dHc（v）=n-k-1。

由引理1.4、引理1.6及定理?xiàng)l件知：

定理 2.2 設(shè)G是n階簡(jiǎn)單圖，n+s≥3，k≥1，n ≥ 2k+1，δ（G）≥ k ≥ s-1，如果，那么G是s-連通圖，除非G∈QP。

證明 構(gòu)造閉包H∶=cln+s-2（G）。假設(shè)G不是s-連通圖，根據(jù)引理1.1知H不是s-連通圖。根據(jù)閉包的定義知，H中任意兩個(gè)不相鄰頂點(diǎn)u，v的度和 dH（u）+dH（v）≤n+s-3，即對(duì) Hc中任意一條邊 uv∈E（Hc）都有

又因?yàn)棣模℅）≥k≥s-1，且H是G的閉包，故有 dH（u）≥ dG（u）≥ k，dH（v）≥ dG（v）≥ k，即有，結(jié)合式（3）可知。

根據(jù)式（4）設(shè) f（x）=x（n-s+1-x），k-s+2≤ x≤n-k-1。利用函數(shù) f（x）的圖像便有 f（x）≥（k-s+2）（n-k-1）當(dāng)且僅當(dāng) x=k-s+2或 x=n-k-1時(shí)等號(hào)成立。因此對(duì)任意邊uv∈E（Hc），

由引理1.4、引理1.6及定理?xiàng)l件知：

利用引理1.2與上述定理相似的證明方法，同理，得到以下推論。

推論2.3 設(shè) G是 n階簡(jiǎn)單圖，n+s≥3，k≥1，n≥2k+1，δ（G）≥k≥s-1，如果，那么G是s-邊-連通圖，除非G∈QP。

推論2.4 設(shè) G是 n階簡(jiǎn)單圖，n-s≥1，k≥1，n≥2k+1，δ（G）≥ k≥ 1-s，如果，那么G是s-路-覆蓋圖，除非G∈QP。

推論2.5 設(shè)G是 n階簡(jiǎn)單圖，n+s≥1，k≥1，n≥2k+1，δ（G）≥ k≥ s+1，如果，那么G是s-哈密爾頓圖，除非G∈QP。

推論2.6 設(shè) G是 n階簡(jiǎn)單圖，n+s≥1，k≥1，n≥2k+1，δ（G）≥ k≥ s+1，如果，那么G是s-邊-哈密爾頓圖，除非G∈QP。

推論2.7 設(shè)G是 n階簡(jiǎn)單圖，n+s≥0，k≥1，n≥2k+1，δ（G）≥ k ≥ s+2，如果，那么G是s-哈密爾頓-連通圖，除非G∈QP。

推論2.8 設(shè)G是 n階簡(jiǎn)單圖，n-s≥1，k≥1，n ≥ 2k+1，δ（G）≥ k≥n-2s，如果，那么 α（G）≤ s，除非G∈QP。

3 結(jié)論

研究首先找到圖的相應(yīng)性質(zhì)的穩(wěn)定性，構(gòu)造相應(yīng)的閉包，再對(duì)閉包的補(bǔ)圖進(jìn)行討論，最后根據(jù)補(bǔ)圖的無(wú)符號(hào)拉普拉斯譜半徑分別給出了具有較大最小度的圖具有某些特殊性質(zhì)的充分條件，這為我們研究圖的結(jié)構(gòu)性質(zhì)提供了一種行之有效的方法。