亚洲免费av电影一区二区三区,日韩爱爱视频,51精品视频一区二区三区,91视频爱爱,日韩欧美在线播放视频,中文字幕少妇AV,亚洲电影中文字幕,久久久久亚洲av成人网址,久久综合视频网站,国产在线不卡免费播放

        ?

        兩類(lèi)圖族的Merrifield-Simmons指標(biāo)的最大值*

        2013-09-15 11:19:18任勝章鄭國(guó)彪
        關(guān)鍵詞:正整數(shù)等式頂點(diǎn)

        任勝章,鄭國(guó)彪

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

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

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

        在本文中沒(méi)有給出的專(zhuān)業(yè)術(shù)語(yǔ)、記號(hào)可參見(jiàn)文獻(xiàn)[9]。

        1 預(yù)備引理

        引理1[9]設(shè)圖G1和G2是圖G的兩個(gè)分支,則i(G)=i(G1)i(G2)。

        引理2[9]設(shè)圖G是簡(jiǎn)單圖且任意的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ù)取定值時(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ù)取定值時(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時(shí),由引理1,引理2和引理3得到

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

        所以

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

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

        定理2 假設(shè)s1,s2,…,sn都是正整數(shù)且滿足si≥3(i=1,2,…,n),在頂點(diǎn)數(shù)取定值時(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))。

        在證明過(guò)程中,用到的符號(hào)標(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ù)為定值時(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.

        猜你喜歡
        正整數(shù)等式頂點(diǎn)
        過(guò)非等腰銳角三角形頂點(diǎn)和垂心的圓的性質(zhì)及應(yīng)用(下)
        組成等式
        被k(2≤k≤16)整除的正整數(shù)的特征
        關(guān)于頂點(diǎn)染色的一個(gè)猜想
        一個(gè)連等式與兩個(gè)不等式鏈
        周期數(shù)列中的常見(jiàn)結(jié)論及應(yīng)用*
        方程xy=yx+1的全部正整數(shù)解
        巧設(shè)等式
        一類(lèi)一次不定方程的正整數(shù)解的新解法
        速填等式
        成人激情四射网| 亚洲综合网站久久久| 久久香蕉国产线熟妇人妻| 国产av日韩a∨亚洲av电影| 国产人禽杂交18禁网站| 精品熟女视频一区二区三区国产| 在线观看av片永久免费| 999国内精品永久免费视频| 日韩女人毛片在线播放| 久久综合九色综合久久久 | 国产成人无码精品久久久露脸| 欧洲熟妇色xxxx欧美老妇多毛网站| 日本理论片一区二区三区| 日韩人妻大奶子生活片| 99国产精品久久久久久久成人热| 欧美操逼视频| 日本a在线播放| 日本高清在线播放一区二区| 东北少妇不戴套对白第一次| 日日躁夜夜躁狠狠久久av| 亚洲AⅤ男人的天堂在线观看| 日本a级片一区二区三区| 中国午夜伦理片| 色婷婷日日躁夜夜躁| 黄色三级视频中文字幕| 少妇免费av一区二区三区久久 | 国产 精品 自在 线免费| 美丽的熟妇中文字幕| 亚洲国产精品综合久久20| 东风日产车是不是国产的 | 国产精品人人做人人爽人人添 | 国产最新AV在线播放不卡| 国产日本精品一区二区| 极品老师腿张开粉嫩小泬| aaaaa级少妇高潮大片免费看 | 国产精品久久国产精品99| 99热这里只有精品4| 亚洲大胆视频在线观看| 少妇久久久久久被弄高潮| 欧美白人最猛性xxxxx| 97人妻蜜臀中文字幕|