王月卿, 林雅津

(1.閩南師范大學(xué) 計(jì)算機(jī)學(xué)院, 福建 漳州 363000; 2.閩南師范大學(xué) 數(shù)學(xué)與統(tǒng)計(jì)學(xué)院, 福建 漳州 363000)

等式成立當(dāng)且僅當(dāng)G?Sn.

本文討論的圖均為無(wú)向連通圖,設(shè)G=(V,E),其中V(G)為圖G的頂點(diǎn)集,其階數(shù)為n;E(G)為圖G的邊集,其階數(shù)為m;用dv表示與頂點(diǎn)v∈V(G)相關(guān)聯(lián)的的邊數(shù),稱為頂點(diǎn)v的度;頂點(diǎn)數(shù)為n的完全圖,星圖和路分別用Kn,Sn及Pn表示.

用q(G)表示無(wú)符號(hào)拉普拉斯矩陣Q(G)=D(G)+A(G)的譜半徑,即矩陣Q(G)的最大特征值,其中D(G)和A(G)分別為圖G的度對(duì)角矩陣和鄰接矩陣;用λ(G)表示圖G的譜半徑,即矩陣A(G)的最大特征值.

Zhou等[1]定義并研究了圖G的Sum-connectivity指標(biāo),其定義如下:

更多關(guān)于圖的Sum-connectivity指標(biāo)的性質(zhì),可參考文獻(xiàn)1～3.

對(duì)于簡(jiǎn)單圖G,其性質(zhì)可以借助各種形式的圖的拓?fù)渲笜?biāo)來(lái)衡量,對(duì)其各自拓?fù)渲笜?biāo)的研究,目前已有大量的成果.近期,關(guān)于圖的特征值(特別是q(G)和λ(G))與圖的拓?fù)渲笜?biāo)之間關(guān)系的研究受到了廣泛關(guān)注.

本文主要研究的是χ(G)與q(G)之間的關(guān)系,證明了以下結(jié)論.

定理1設(shè)G為具有n≥3個(gè)頂點(diǎn)的連通圖,則

等號(hào)成立當(dāng)且僅當(dāng)G?Sn.

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

首先,我們將給出一些在證明過(guò)程中將會(huì)用到的已有結(jié)論.在文獻(xiàn)4～5中分別給出了無(wú)符號(hào)拉普拉斯譜半徑和鄰接矩陣譜半徑的上界.

引理1.1[6]設(shè)G為具有n個(gè)頂點(diǎn),m條邊的連通圖,則

等號(hào)成立當(dāng)且僅當(dāng)G?Kn或G?Sn.

引理1.2[7]設(shè)G為具有n個(gè)頂點(diǎn),m條邊的連通圖,λ(G)為鄰接矩陣的譜半徑,則

等號(hào)成立當(dāng)且僅當(dāng)G?Kn或G?Sn.

引理1.3[8]設(shè)G為具有n個(gè)頂點(diǎn)的任意連通圖,λ(G)為鄰接矩陣的譜半徑,則

引理1.4[1]令G為具有m條邊的連通圖,則

引理1.5設(shè)G為具有n個(gè)頂點(diǎn),m條邊的連通圖,則

證明由引理1.3和1.4,則

結(jié)論成立.

2 定理1的證明

在給出定理1的證明之前,首先證明以下事實(shí),設(shè)G為具有n≥5個(gè)頂點(diǎn),m條邊的連通圖,則有

引理2.1設(shè)G為具有n≥5個(gè)頂點(diǎn),m條邊的簡(jiǎn)單連通圖,則

證明因?yàn)镚為簡(jiǎn)單連通圖,所以有m≥n-1.以下將根據(jù)m的大小分兩種情況對(duì)引理2.1進(jìn)行證明.

(1)當(dāng)m=n-1時(shí)

令

則

(1)

其中

g(m)=(m-n+1)[nm2+(n-4)(n-1)m-(n3-4n2+4n-2)].

(2)當(dāng)時(shí)m≥n時(shí)

注意到

g(m)=(m-n+1)[nm2+(n-4)(n-1)m-(n3-4n2+4n-2)],

顯然

有g(shù)(m)≥0.

因?yàn)?/p>

所以有

綜上所述,當(dāng)m≥n-1時(shí),有

引理2.2設(shè)G為具有n≥5個(gè)頂點(diǎn),m條邊的簡(jiǎn)單連通圖.若

下面分兩種情況進(jìn)行討論:

(2)當(dāng)G?Sn時(shí),m=n-1,則有

由引理2.1和2.2,可得以下結(jié)論.

引理2.3設(shè)G為具有n≥5個(gè)頂點(diǎn)的簡(jiǎn)單連通圖.則

等號(hào)成立當(dāng)且僅當(dāng)G?Sn.

引理2.4設(shè)G為具有n=3個(gè)頂點(diǎn)的簡(jiǎn)單連通圖.則

等號(hào)成立當(dāng)且僅當(dāng)G?S3.

表1 頂點(diǎn)數(shù)n=3

引理2.5設(shè)G為具有n=4個(gè)頂點(diǎn)的簡(jiǎn)單連通圖.則

等式成立當(dāng)且僅當(dāng)G?S4.

表2 頂點(diǎn)數(shù)n=4

定理1的證明由引理2.3, 2.4, 2.5易得.