田文文，田雙亮,柴文麗

( 1.西北民族大學(xué) 數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院，甘肅蘭州730030；2.西北民族大學(xué)美術(shù)學(xué)院，甘肅 蘭州730030)

一類(n,n+2)-圖關(guān)于Merrifield-Simmons指標(biāo)和Hosoya指標(biāo)的排序

田文文1，田雙亮1,柴文麗2

( 1.西北民族大學(xué) 數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院，甘肅蘭州730030；2.西北民族大學(xué)美術(shù)學(xué)院，甘肅 蘭州730030)

Merrifield-Simmons指標(biāo)和Hosoya指標(biāo)是化學(xué)圖論中兩個(gè)重要的拓?fù)渲笜?biāo)．圖G的Merrifield-Simmons指標(biāo)表示該圖中所有獨(dú)立集的數(shù)目，圖G的Hosoya指標(biāo)表示該圖中所有匹配的數(shù)目．文中研究了一類(n,n+2)圖T(k)的Merrifield-Simmons指標(biāo)和Hosoya指標(biāo)，并給出了該圖類關(guān)于這兩種拓?fù)渲笜?biāo)的排序．

n,n+2-圖；Merrifield-Simmons指標(biāo)；Hosoya指標(biāo)；排序

0 引言

Merrifield-Simmons指標(biāo)是在1989年由美國(guó)化學(xué)家Richard E．Merrifield和Howard E．Simmons在文獻(xiàn)[1]中引入的化學(xué)拓?fù)渲笜?biāo)，它表示圖G中所有獨(dú)立集的數(shù)目，記為σ(G)，該指標(biāo)與物質(zhì)的沸點(diǎn)有著密切的聯(lián)系．Hosoya指標(biāo)是由日本化學(xué)家Haruo Hosoya于1971年在文獻(xiàn)[2]中提出并進(jìn)行研究的.它表示圖G中所有匹配的數(shù)目，記為μ(G).該指標(biāo)與物質(zhì)的沸點(diǎn)、熵、化學(xué)鍵的計(jì)算和化學(xué)結(jié)構(gòu)等有著密切的聯(lián)系．這兩個(gè)拓?fù)渲笜?biāo)在結(jié)構(gòu)化學(xué)中有著重要的意義，它們常常被用來(lái)描述有機(jī)化合物的物理化學(xué)特征與藥理特征，且有著較為廣泛的應(yīng)用，相關(guān)的應(yīng)用參見(jiàn)文獻(xiàn)[1,3～4]．文獻(xiàn)[5～8]中確定了雙圈圖中最大和最小的Merrifield-Simmons指標(biāo)和Hosoya指標(biāo)，并刻畫(huà)了相應(yīng)的極圖.文獻(xiàn)[9]中研究了一類特殊雙圈圖的兩種指標(biāo)的排序.文獻(xiàn)[10～12]中研究了三圈圖中最大和最小的Merrifield-Simmons指標(biāo)和Hosoya指標(biāo)，并刻畫(huà)了相應(yīng)的極圖．本文主要研究了一類特殊(n,n+2)-圖T(k)關(guān)于Merrifield-Simmons指標(biāo)和Hosoya指標(biāo)的排序問(wèn)題．

(n,n+2)-圖表示一類由n個(gè)頂點(diǎn)和n+2條邊構(gòu)成的圖．圖T(k)表示一類由三個(gè)圈Cp、Cq和Cm構(gòu)成的(n,n+2)-圖，其中Cp和Cq與Cm的兩個(gè)接點(diǎn)分別為υ和u，且d(u,υ)=k，如圖1所示．

圖1 圖T(k)

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

在證明主要結(jié)論之前，先介紹以下幾個(gè)相關(guān)引理：

引理1[3]是一個(gè)簡(jiǎn)單的連通圖，對(duì)任意的u,υ∈V(G)，uυ∈E(G)，則①σ(G)=σ(G-υ)+σ(G-NG[υ])；②σ(G)=σ(G-uυ)-σ(G-(NG[u]∪NG[υ])).

引理3[3]若G1，G2，…，Gk是圖G的連通分支，則

引理4[3]對(duì)于n階的路Pn，有σ(Pn)=fn+2;μ(Pn)=fn+1.

引理5[3]對(duì)于n階的圈Cn，有σ(Cn)=fn+1+fn-1；μ(Cn)=fn+1+fn-1.

由引理1～5可易得以下結(jié)論：

圖2 圖H

引理7 對(duì)于如圖2所示的H，有

σ(H)=fm+2fn+2fq+1+fm+1fn+1fq-1.

μ(H)=(fq+1+fq-1)·fm+1fn+1+fq·(fmfn+1+fm+1fn).

2 主要結(jié)果及其證明

該類特殊圖T(k)關(guān)于Merrifield-Simmons指標(biāo)和Hosoya指標(biāo)的排序，可以得出以下結(jié)論：

σ(T(1))<σ(T(3))<…<σ(T(2s+1))<σ(T(2s+2t))<…<σ(T(4))<σ(T(2)).

證明 如圖1所示，由引理可知

σ(T(k))=fp+1·(fk+1fm-k+1fq+1+fkfm-kfq-1)+fp-1·(fkfm-kfq+1+fk-1fm-k-1fq-1).

同理可得

σ(T(k+1))=fp+1·(fk+2fm-kfq+1+fk+1fm-k-1fq-1)+fp-1·(fk+1fm-k-1fq+1+fkfm-k-2fq-1)，

σ(T(k+2))=fp+1·(fk+3fm-k-1fq+1+fk+2fm-k-2fq-1)+fp-1·(fk+2fm-k-2fq+1+fk+1fm-k-3fq-1).

下面比較σ(T(k))、σ(T(k+1))、σ(T(k+2))三者之間的大小關(guān)系.

由引理6可得

σ(T(k+1))-σ(T(k))=fp+1·[fq+1·(fk+2fm-k-fk+1fm-k+1)+fq-1·

(fk+1fm-k-1-fkfm-k)]+fp-1·[fq+1·(fk+1fm-k-1-fkfm-k)+fq-1·(fkfm-k-2-fk-1fm-k-1)]

(lm-2k+lm-2k-2)+fp-1fq-1·(-lm-2k-lm-2k-2)]

=(-1)k+1·fpfqfm-2k-1.

故當(dāng)k為偶數(shù)時(shí)，有σ(T(k+1))<σ(T(k))；當(dāng)k為奇數(shù)時(shí)，有σ(T(k+1))>σ(T(k)).

σ(T(k+2))-σ(T(k))=fp+1·[fq+1·(fk+3fm-k-1-fk+1fm-k+1)+fq-1·(fk+2fm-k-2-fkfm-k)]

+fp-1·[fq+1·(fk+2fm-k-2-fkfm-k)+fq-1·(fk+1fm-k-3-fk-1fm-k-1)]

(lm-2k+lm-2k-4)+fp-1fq-1·(lm-2k-4-fm-2k)]

=(-1)k+1·fpfqfm-2k-2.

故當(dāng)k為偶數(shù)時(shí)，有σ(T(k+2))<σ(T(k))；當(dāng)k為奇數(shù)時(shí)，有σ(T(k+2))>σ(T(k)).

σ(T(1))<σ(T(3))<…<σ(T(2s+1))<σ(T(2s+2t))<…<σ(T(4))<σ(T(2)).

μ(T(1))>μ(T(3))>…>μ(T(2s+1))>μ(T(2s+2t))>…>μ(T(4))>μ(T(2)).

證明 如圖1所示，由引理可知

μ(T(k))=(fp+1+fp-1)·[(fq+1+fq-1)·fkfm-k+fq·(fk-1fm-k+fkfm-k-1]

+fp·[(fq+1+fq-1)(fkfm-k-1+fk-1fm-k)+fq·(fkfm-k-2+2fk-1fm-k-1+fk-2fm-k)].

同理可得

μ(T(k+1))=(fp+1+fp-1)·[(fq+1+fq-1)·fk+1fm-k-1+fq·(fkfm-k-1+fk+1fm-k-2)]

+fp·[(fq+1+fq-1)(fk+1fm-k-2+fkfm-k-1)+fq·(fk+1fm-k-3+2fkfm-k-2+fk-1fm-k-1)]，

μ(T(k+2))=(fp+1+fp-1)·[(fq+1+fp-1)·fk+2fm-k-2+fq·(fk+1fm-k-2+fk+2fm-k-3)]

+fp·[(fq+1+fq-1)(fk+2fm-k-3+fk+1fm-k-2)+fq·(fk+2fm-k-4+2fk+1fm-k-3+fkfm-k-2)].

下面比較μ(T(k))、μ(T(k+1))、μ(T(k+2))三者之間的大小關(guān)系.

由引理6可得

μ(T(k+1))-μ(T(k))=(fp+1+fp-1)·[(fq+1+fq-1)(fk+1fm-k-1-fkfm-k)+fq·

(fk+1fm-k-2-fk-1fm-k)]+fp· [(fq+1+fq-1)(fk+1fm-k-2-fk-1fm-k)+fq·

(fk+1fm-k-3+fkfm-k-2-fk-1fm-k-1-fk-2fm-k)]

fp·(fq+1+fq-1)(lm-2k-3-lm-2k+1)+fpfq·(lm-2k+1-lm-2k-3)]

又(lm-2k+lm-2k+2)-(lm-2k+lm-2k-2)=lm-2k+1+lm-2k-1>0

(fp+1+fp-1)(fq+1+fq-1)-(fqfp+1+fqfp-1+2fq-1fp)=fq-1·(fp+1+fp-1+fp-3)>0.

所以(fp+1+fp-1)(fq+1+fq-1)(lm-2k+lm-2k+2)-(fqfp+1+fqfp-1+2fq-1fp)(lm-2k+lm-2k-2)>0.

故當(dāng)k為偶數(shù)時(shí)，有μ(T(k+1))>μ(T(k))；當(dāng)k為奇數(shù)時(shí)，有μ(T(k+1))<μ(T(k)).

μ(T(k+2))-μ(T(k))=(fp+1+fp-1)[(fq+1+fq-1)(fk+2fm-k-2-fkfm-k)+fq·

(fk+1fm-k-2+fk+2fm-k-3-fk-1fm-k-fkfm-k-1)]+fm· [(fq+1+fq-1)

(fk+2fm-k-3+fk+1fm-k-2-fkfm-k-1fk-1fm-k)+fq·

(fk+2fm-k-4+2fk+1fm-k-3-2fk-1fm-k-1-fk-2fm-k)]

fp·(fq+1+fq-1)(lm-2k-4-lm-2k)+fpfq·(lm-2k-1+lm-2k-3)]

=(-1)k·4fp-1fq-1fm-2k-2.

故當(dāng)k為偶數(shù)時(shí)，有μ(T(k+2))>μ(T(k))；當(dāng)k為奇數(shù)時(shí)，有μ(T(k+2))<μ(T(k)).

μ(T(1))>μ(T(3))>…>μ(T(2s+1))>μ(T(2s+2t))>…>μ(T(4))>μ(T(2)).

通過(guò)觀察可知，該類(n,n+2)-圖T(k)關(guān)于Merrifield-Simmons指標(biāo)和Hosoya指標(biāo)的排序恰好相反．

[1] Merrifield R E，Simmons H E．Topological Methods in Chemistry[M].New York：Wiley，1989．

[2] Hosoya H．Topological index[J].Bull Chem Soc Japan，1971，44：2332-2339．

[3] Gutman I，Polansky O E．Mathematical Concepts in Organic Chemistry[M]．Berlin：Spring-er，1986．

[4] Gutman I，Cyvin S J．Introduction to the Theory of Benzenoid Hydrocarbons[M]．Berlin：Springer，1989．

[5] Deng H Y，Chen S B，Zhang J．The Merrifield-Simmons index in(n,n+1)-graphs[J]．Journal of Mathematical Chemistry,2008，43(1)：75-91．

[6] Deng H Y．The smallest Merrifield-Simmons index of(n,n+1)-graphs[J]．Math Comput Model,2009，49(1-2)：320-326．

[7] Deng H Y．The smallest Hosoya index in(n,n+1)-graphs[J]．Journal of Mathematical Chemistry，2008，43(1)：119-133．

[8] Xu Kexiang，Gutman I．The Greatest Hosoya Index of Bicyclic Graphs with Given Maximum Degree[J]．MATCH Commun Math Comput Chem,2011，66(3)：795-824．

[9] 周旭冉，王力工．一類雙圈圖的兩種指標(biāo)的排序[J]．山東大學(xué)學(xué)報(bào)(理學(xué)版),2011，46(11)：44-47．

[10] Zhu Zhongxun，Li Shuchao，Tan Liansheng．Tricyclic graphs with maximum Merrifield-Simmons index[J]．Discrete Applied Mathematics,2010，158(3)：204-212．

[11] Dolati A，Haghighat M，Golalizadeh S，Safari M．The Smallest Hosoya index of Connected Tricyclic Graphs[J]．MATCH Commun Math Comput Chem,2011，65(1)：57-70．

[12] Zhu Zhongxun，Yu Qigang．The number of independent sets of tricyclic graphs[J]．Applied Mathematics Letters,2012，25(10)：1327-1334．

[13] Bondy J A，Murty U S R．Graph theory with applications[M]．New York：The Macmillan Press，1976．

[14] Stephan G Wagner．Extremal trees with respect to Hosoya index and Merrifield-Simmons index[J]．MATCH Commun Math Comput Chem,2007，57(1)：221-233．

2015-05-20

國(guó)家民委科研項(xiàng)目(14XBZ018)；甘肅省自然科學(xué)基金(145RJZA158)；西北民族大學(xué)科研創(chuàng)新團(tuán)隊(duì)計(jì)劃資助項(xiàng)目；中央高?；究蒲袠I(yè)務(wù)費(fèi)專項(xiàng)資金項(xiàng)目(31920140059)．

田文文(1987—)，男，甘肅天水人，科員，主要從事圖論與組合優(yōu)化方面的研究.

O157.5

A

1009-2102(2015)02-0012-04