亚洲免费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永久无码一区二区三区| 国产在线精彩自拍视频| 日韩久久一级毛片| 在线看片免费人成视频久网下载| 日本二区在线视频观看| 亚洲区1区3区4区中文字幕码| 激情五月婷婷综合| 一本一道av中文字幕无码| 国产内射爽爽大片| 午夜麻豆视频在线观看| 国产片三级视频播放| 国产96在线 | 亚洲| 亚洲综合在线一区二区三区| 中文字幕亚洲精品一区二区三区| 免费女同毛片在线不卡| 亚洲欧美日韩专区一| 国产av精国产传媒| 成人免费无码大片a毛片抽搐色欲| 日本红怡院东京热加勒比| 午夜三级网| 性一乱一搞一交一伦一性| 24小时日本在线视频资源| 久久久国产精品123| 国产自拍视频一区在线| 国产又粗又猛又黄色呦呦| 亚洲aⅴ无码国精品中文字慕| 精品熟女日韩中文十区| 久久99精品国产麻豆不卡| 亚洲 日本 欧美 中文幕| 亚洲无精品一区二区在线观看| 国产精品一区一区三区| 亚洲AV秘 无套一区二区三区| 青青在线精品2022国产| 久久午夜伦鲁片免费无码| 日本久久高清一区二区三区毛片| 欧美丰满熟妇xxxx性ppx人交| 日本精品免费看99久久| 国产精品又爽又粗又猛又黄| 韩国免费一级a一片在线| 日韩久久av电影|