兩類圖族的Merrifield－Simmons指標(biāo)的最大值*

任勝章，鄭國彪

(1.天水師范學(xué)院數(shù)學(xué)與統(tǒng)計學(xué)院，甘肅天水 741001;2.青海民族大學(xué)數(shù)學(xué)系，青海西寧 810007)

設(shè)圖G=(V，E)是簡單的連通圖，并且V(G)是它的頂點(diǎn)集和E(G)是它的邊集。對一個圖G的任意兩個頂點(diǎn)u和v，如果它們不相鄰，則稱它們是相互獨(dú)立的。一個頂點(diǎn)集V(G)的子集I，如果它的任意兩個頂點(diǎn)都相互獨(dú)立，則稱它是圖G的一個獨(dú)立集。用i(G)表示圖G的獨(dú)立集的個數(shù)，在化學(xué)中i(G)也被稱為Merrifield－Simmons指標(biāo)，此指標(biāo)與化學(xué)分子的許多物理、化學(xué)性質(zhì)密切相關(guān)，如分子的熔點(diǎn)、沸點(diǎn)等;對該指標(biāo)的研究成果很多，參見文獻(xiàn) ［1－8］。

設(shè)Ck、Pk和Wk分別表示頂點(diǎn)數(shù)分別為k，k，k+1的圈，路和輪。則用Q(Ck;Cs1，Cs2，…，Csk)表示圖族圈粘接圈是由圈Ck的每個頂點(diǎn)vi(i=1，2，…，k)分別點(diǎn)粘接圈Csi(i=1，2，…，k)而得到的圖;用Q(Pk;Cs1，Cs2，…，Csk)表示圖族路粘接圈是由路Pk的每個頂點(diǎn)vi(i=1，2，…，k)分別點(diǎn)粘接圈Csi(i=1，2，…，k)而得到的圖;用Q(Wk;Cs1，Cs2，…，Csk)表示圖族輪粘接圈是由輪Wk的每個頂點(diǎn)vi(i=1，2，…，k)(除中心頂點(diǎn)外)分別點(diǎn)粘接圈Csi(i=1，2，…，k)而得到的圖。本文通過對圖族Q(Ck;Cs1，Cs2，…，Csk)，Q(Wk;Cs1，Cs2，…，Csk)的Merrifield－Simmons指標(biāo)進(jìn)行研究，刻畫出了這兩類圖族的Merrifield－Simmons指標(biāo)在頂點(diǎn)數(shù)一定時，取得最大值的圖分別是Q(Ck;C4，C4，…，C4，Cs1+s2+…+sk－4(k－1))，Q(Wk;C4，C4，…，C4，Cs1+s2+…+sk－4(k－1))。

在本文中沒有給出的專業(yè)術(shù)語、記號可參見文獻(xiàn)［9］。

1 預(yù)備引理

引理1［9］設(shè)圖G1和G2是圖G的兩個分支，則i(G)=i(G1)i(G2)。

引理2［9］設(shè)圖G是簡單圖且任意的v∈V(G)，則有i(G)=i(G－v)+i(G－NG［v］)，其中NG［v］是v的閉鄰集。

引理 4［3］設(shè)圖Q(Pk;Cs1，Cs2，…，Csk)是圖族路粘接圈，在頂點(diǎn)數(shù)取定值時，則有i(Q(Pk;Cs1，Cs2，…，Csk))≤i(Q(Pk;C4，C4，…，C4，Cs1+s2+…+sk－4(k－1)))，等式成立當(dāng)且僅當(dāng)，Q(Pk;Cs1，Cs2，…，Csk)?Q(Pk;C4，C4，…，C4，Cs1+s2+…+sk－4(k－1))。

2 主要結(jié)論

定理1 假設(shè)s1，s2，…，sk都是正整數(shù)且滿足2≤s1≤s2≤…≤sk，在頂點(diǎn)數(shù)取定值時，則有:i(Ps1∪Ps2∪…∪Psk)≥i(P3∪P3∪…∪P3∪Ps1+s2+…+sk－3(k－1))，等式成立當(dāng)且僅當(dāng)，Ps1∪Ps2∪… ∪PskP3∪P3∪ … ∪P3∪Ps1+s2+…+sk－3(k－1)。

證明 (歸納法)假設(shè)n是路并圖Ps1∪Ps2∪…∪Psk的分支數(shù)，那么當(dāng)n=2時，由引理1，引理2和引理3得到

等號成立當(dāng)且僅當(dāng)，s1=3。所以當(dāng)n=2時，結(jié)論成立。假設(shè)當(dāng)n=k時，結(jié)論成立。即i(Ps1∪Ps2∪…∪Psk)≤i(P3∪P3∪…∪P3∪Ps1+s2+…+sk－3(k－1))，那么當(dāng)n=k+1 時，由歸納假設(shè)，我們得到

所以

等式成立當(dāng)且僅當(dāng)，sk+1=3。

由上面兩個證明過程可知，當(dāng)n取遍所有大于2的自然數(shù)時，結(jié)論都成立。

定理2 假設(shè)s1，s2，…，sn都是正整數(shù)且滿足si≥3(i=1，2，…，n)，在頂點(diǎn)數(shù)取定值時，則有

并且等式成立當(dāng)且僅當(dāng)

證明 由引理4和定理1，我們得到

同理得到

因此

并且等式成立當(dāng)且僅當(dāng)Q(Cn;Cs1，Cs2，…，Csn)?Q(Cn;C3，C3，…，C3，Cs1+s2+…+sn－3(n－1))。

在證明過程中，用到的符號標(biāo)記T4，k=Q(Pk;C4，C4，…，C4)(k=1，2，…，n)，因此結(jié)論成立。

定理3 假設(shè)s1，s2，…，sn都是正整數(shù)且滿足si≥3(i=1，2，…，n)，在頂點(diǎn)數(shù)為定值時，則有

并且等式成立當(dāng)且僅當(dāng)

證明 由引理2、定理1和定理2，可以得到

所以定理3成立。

［1］ZHAO H，LI I.On the Fibonacci numbers of trees［J］.Fibonacci Quart，2006，44(1):32 －38.

［2］PRODINGER H，TICHY R F.Fibonacci numbers of graphs［J］.The Fibonacci Quart，1982，20(1):16 －21.

［3］REN S Z，HE W S.The study of σ index onQ(Pk;Cs1，Cs2，…，Csk)graphs［J］.SCIENTIA MAGNA，2008，4(4):40－45.

［4］REN S Z，HE W S.The Merrifield－Simmons index in(n，n+1)－graphs［J］.SCIENTIA MAGNA，2009，5(2):6－14.

［5］REN S Z.Merrifield－Simmons index of tree－type hexagonal systems［J］.MATCH Commun Math Comput Chem，2011，66(3):837－848.

［6］REN S Z，HE W S.The study of σindex onQ(Sk;Cs1，Cs2，…，Csk)graphs［J］.SCIENTIA MAGNA，2008，4(2):49－55.

［7］GUTMAN I，CYVIN S J.Introduction to the theory of Benzenoid hydrocarbons［M］.Berlin:Springer，1989.

［8］SHIU W C.Extremal Hosoya index and Merrifield－Simmons of hexagonal spiders［J］.Discr Apple Math，2008，156(1):2978－2985.

［9］BONDY J A，MURTY U S R.Graph theory with application［M］.New York，1976.