利用Wiener指數(shù)、hyper-Wiener指數(shù)及Harary指數(shù)給出泛圈圖的充分條件

胡啟明， 許 歡， 葉 銘

(合肥幼兒師范高等專科學(xué)校 公共教學(xué)部，安徽 合肥 230013)

引 言

設(shè)G(V,E)是n階簡單連通圖，頂點(diǎn)用vi(1in)表示，頂點(diǎn)集{v1,v2,…,vn}用V(G)(或V)表示；邊集用E(G)(或E)表示，其元素可簡記作vivj(1i,jn)，稱為邊[1]。稱頂點(diǎn)vi(或vj)與邊vivj是關(guān)聯(lián)的，稱邊vivj的兩個端點(diǎn)vi和vj是相鄰的。若圖G中的任意一個頂點(diǎn)vi(1in)與其他頂點(diǎn)都相鄰，則稱G為完全圖，記作Kn。用或(G)c)表示圖G的補(bǔ)圖，其中是由G中所有不相鄰的兩個頂點(diǎn)連成的邊組成的集合。圖G中與vi關(guān)聯(lián)的邊數(shù)稱為頂點(diǎn)vi的度，用dG(vi)表示，圖G的最小度記為δ(G)。圖G中頂點(diǎn)vi和vj之間所有路的最小長度稱為vi與vj之間的距離，記作dG(vi,vj)。

若對于任意的正整數(shù)k(3k

用G1∪G2表示G1和G2的并圖，其中V(G1∪G2)=V(G1)∪V(G2)，E(G1∪G2)=E(G1)∪E(G2)；如果G1和G2沒有公共頂點(diǎn)，G1和G2的并圖記為G1+G2；若G1=G2=…=Gk，則G1∪G2∪…∪Gk記為kG1。

用G1∨G2表示G1和G2的聯(lián)圖，其等于((G1)c∪(G2)c)c，即V(G1∨G2)=V(G1)∪V(G2)，E(G1∨G2)為G1的邊、G2的邊和由G1中每個頂點(diǎn)與G2中每個頂點(diǎn)連成的邊組成的集合。

圖G的Wiener指數(shù)[2]記作W(G)，是指G中任意兩個頂點(diǎn)vi和vj的距離之和，即

圖G的hyper-Wiener指數(shù)[3-4]是Wiener指數(shù)的推廣，記作WW(G)，定義為

圖G的Harary指數(shù)[5]記作H(G)，是指G中任意兩個頂點(diǎn)vi和vj的距離倒數(shù)之和，即

對于任意給定的無向圖G，怎樣判斷它是否包含一個哈密爾頓圈？這就是舉世聞名的NP完全問題。因?yàn)閳D的拓?fù)渲笖?shù)能很好的反映圖的結(jié)構(gòu)性質(zhì)且便于計(jì)算，近年來人們試圖利用圖的拓?fù)渲笖?shù)來刻畫圖的哈密爾頓性，如2013年華洪波等人[6]首次用Harary指數(shù)給出了連通圖有哈密爾頓路的一個充分條件。隨后曾婷[7]利用Harary指數(shù)給出平衡二部圖有哈密爾頓圈的一個充分條件。楊立輝[8]給出了連通圖存在哈密爾頓路的關(guān)于Wiener指數(shù)的一個充分條件。Rao Li[9,10]分別給出了連通圖是哈密爾頓圖和哈密爾頓連通圖的關(guān)于Harary指數(shù)和Wiener指數(shù)的充分條件。劉瑞芳[11,12]延伸了[7,8]中的結(jié)果。華洪波等人[13]給出了給定最小度的連通圖、平衡二部圖可跡性與哈密爾頓性的關(guān)于Harary指數(shù)和Wiener指數(shù)的充分條件。基于前面的研究基礎(chǔ)，馮立華等人在[14]中又給出了k-哈密爾頓，k-路覆蓋，k-邊哈密爾頓的關(guān)于Harary指數(shù)和Wiener指數(shù)的充分條件。特別是最近舒阿秀等[15]研究了泛圈圖的拓?fù)渲笖?shù)條件，利用圖及其補(bǔ)圖的Wiener指數(shù)、hyper-Wiener指數(shù)，給出了具有最小度條件的簡單連通圖是泛圈圖的充分條件；余桂東等[16]給出了泛圈圖的新的邊數(shù)條件，以及譜半徑和無符號Laplacian譜半徑條件。受文獻(xiàn)[15,16]的啟發(fā)，本文利用文獻(xiàn)[16]中泛圈圖的新的邊數(shù)條件，利用圖及其補(bǔ)圖的Wiener指數(shù)、hyper-Wiener指數(shù)，Harary指數(shù)給出了具有最小度條件的簡單連通圖是泛圈圖的充分條件，其中Wiener指數(shù)、hyper-Wiener指數(shù)的充分條件優(yōu)化了文獻(xiàn)[15]中的結(jié)論。

1 相關(guān)引理

記NP1={K2∨(Kn-4+2K1),K5∨6K1,K3∨(K2+3K1),K3∨(K1+K1，4),K3∨(K2+K1，3),(K2∨2K1∨5K1,K4∨5K1,K1，2∨4K1,K2∨(K1+K1，3),K3∨4K1}。

記NPC={K4∨5K1,K2∨(K3+2K1),K3∨4K1,K1，2∨4K1,K2∨(K1+K1，3),K2∨(K2+2K1),K1∨2K2,K2∨3K1}。

2 主要結(jié)論

定理2.1設(shè)簡單連通圖G的頂點(diǎn)數(shù)為n(n≥5)，δ(G)≥2。若

W(G)

則G要么是一個泛圈圖，要么是一個二部圖，要么屬于NP1。

于是有

=n(n-1)-m

這與條件W(G)矛盾。

下面討論G∈NP1的情況：

綜上，當(dāng)G∈NP1時，有W(G)

故G是一個泛圈圖，或是一個二部圖，或?qū)儆贜P1。

推論2.2設(shè)G為n(n≥9)階簡單連通圖，δ≥2，如果

W(G)

則G是一個泛圈圖，除非G是一個二部圖或G∈{K4∨5K1，K3∨4K1}。

定理2.3[15]設(shè)G為n階簡單連通圖，δ≥2，如果

W(G)

則G是一個泛圈圖，除非G是一個二部圖或G∈NPC。

注：由于{K4∨5K1，K3∨4K1}?NPC，故n≥9時，定理2.1推廣了定理2.3。

則G要么是泛圈圖，要么是一個二部圖。

于是有

則G是一個泛圈圖，除非G是一個二部圖。

定理2.6設(shè)簡單連通圖G的頂點(diǎn)數(shù)為n(n≥5)，δ(G)≥2。若

WW(G)

則G要么是一個泛圈圖，要么是一個二部圖，要么屬于NP1。

于是有

這與所給條件WW(G)矛盾。

下面討論G∈NP1的情況：

綜上，當(dāng)G∈NP1時，有WW(G)

故G是一個泛圈圖，或是一個二部圖，或G∈NP1。

推論2.7設(shè)G為n(n≥9)階簡單連通圖，δ≥2，如果

WW(G)

則G是一個泛圈圖，除非G是一個二部圖或G∈{K4∨5K1，K3∨4K1}。

定理2.8[15]設(shè)G為n階簡單連通圖，δ≥2，如果

WW(G)

則G是一個泛圈圖，除非G是一個二部圖或G∈NPC。

注：由于{K4∨5K1，K3∨4K1}?NPC，故n≥9時，定理2.6推廣了定理2.8。

則G要么是一個泛圈圖，要么是一個二部圖。

于是有

則G是一個泛圈圖，除非G是一個二部圖。

定理2.11設(shè)簡單連通圖G的頂點(diǎn)數(shù)為n(n≥5)，δ(G)≥2。若

則G要么是一個泛圈圖，要么是一個二部圖，要么屬于NP1。

于是有

下面討論G∈NP1的情況：

故假設(shè)不成立，則G是一個泛圈圖，或是一個二部圖，或G∈NP1。

則G要么是泛圈圖，要么是一個二部圖。

于是有