劉巧云，吳廷增

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

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

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

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

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

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

其中:p(G,k)為G中選擇k條兩兩不相連的邊數(shù)的方法,t是G中選擇k條兩兩不相連的邊的最大數(shù).對(duì)任意圖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 長(zhǎng)度為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中至少有兩個(gè)大于等于2,即a+b≥3.產(chǎn)生矛盾.此種情況不可能出現(xiàn).

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

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

case 1:若a<3(即a=2)或b<2(即b=1)時(shí),此時(shí)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,此時(shí)Hosoya指標(biāo)最小.

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

case 1:若a<2(即a=1)時(shí),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時(shí),g2(n)

4 Hosoya指標(biāo)排序

研究有n個(gè)頂點(diǎ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é) 語(yǔ)

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