直徑為3的單圈圖的極小Hosoya指標(biāo)

劉巧云，吳廷增

(青海民族大學(xué) 數(shù)學(xué)與統(tǒng)計學(xué)院，西寧 810007)

自Hosoya[1]提出這一拓?fù)渲笜?biāo)以來, 很多學(xué)者都研究過Hosoya指標(biāo)[2-6]. 本文基于Hosoya指標(biāo)定義, 提出和計算了直徑為3的n階單圈圖的Hosoya指標(biāo)計算公式并得到了具有最小、次小的Hosoya指標(biāo)的極圖, 并由此得到直徑為3的n階單圈圖的Hosoya指標(biāo)排序.

1 預(yù)備知識

本文僅考慮無向簡單圖.記圖G(V,E), 其中V代表圖的頂點集合,E代表圖的邊集合.具有n個頂點,m條邊的圖記為G(n,m)圖.當(dāng)n=m且n≥3時, 這一類圖G(n,n)稱為單圈圖.

對于兩個頂點u和v(u≠v),u和v之間的距離是u和v之間最短路的邊數(shù).一個圖的直徑是G中任意兩點間距離的最大值.

定義1[1]圖G的Hosoya指標(biāo)計算式為:

其中:p(G,k)為G中選擇k條兩兩不相連的邊數(shù)的方法,t是G中選擇k條兩兩不相連的邊的最大數(shù).對任意圖G(n,m),p(G,0)=1,p(G,1)=m.

2 直徑為3的單圈圖的最小Hosoya指標(biāo)

下面我們分別討論Ui(i=1,2,3,4)中的具有最小Hosoya指標(biāo)的圖需要滿足的條件.

圖1 長度為3的四種單圈圖 Fgure 1 The four unicycle graphs with diameter 3

case 2:若a+b<3, 只能取a+b=2, 但是G2需滿足a+b+c=n,a≥1,b≥1,c≥1,且a,b,c中至少有兩個大于等于2,即a+b≥3.產(chǎn)生矛盾.此種情況不可能出現(xiàn).

綜上所述,當(dāng)n≥6時,f2(n)

3 直徑為3的單圈圖的次小Hosoya指標(biāo)

case 1:若a<3(即a=2)或b<2(即b=1)時,此時Hosoya指標(biāo)最小.

證明設(shè)G2∈U2, 且1≤a≤b≤c.利用定理2, 有z(G2)=abc+a+b+c.

case 1:若a+b<4, 即a+b=3,此時Hosoya指標(biāo)最小.

case 2:若a<2, 即a=1時,Hosoya指標(biāo)最小.

case 1:若a<2(即a=1)時,Hosoya指標(biāo)最小.

g4(n)-g1(n)=(8n-32)-(6n-22)=2n-10>0,從而g4(n)>g1(n).g1(n)-g3(n)=(6n-22)-(5n-15)=n-7>0, 從而g1(n)>g3(n).g3(n)-g2(n)=(5n-15)-(4n-12)=n-3>0, 從而g3(n)>g2(n).

綜上所述, 當(dāng)n≥7時,g2(n)

4 Hosoya指標(biāo)排序

研究有n個頂點的直徑為3的單圈圖Ui(i=1,2,3,4)的Hosoya指標(biāo)排序問題.記z(G1)=h1(a,b),z(G2)=h2(a,b),z(G3)=h3(a,b),z(G4)=h4(a,b).

定理12U2的Hosoya指標(biāo)排序情況:

5 結(jié) 語

本文得到了直徑為3的n階單圈圖的Hosoya指標(biāo)計算公式并得到了具有最小、次小的Hosoya指標(biāo)的極圖, 并由此得到直徑為3的n階單圈圖的Hosoya指標(biāo)排序. 今后可以繼續(xù)研究直徑更大的情況下的Hosoya指標(biāo)與實際應(yīng)用問題.