路徑冪圖、Flower Snark圖及多錐圖獨(dú)立數(shù)

徐連誠, 楊元生, 夏尊銓

(1.大連理工大學(xué)數(shù)學(xué)科學(xué)學(xué)院,遼寧大連 116024;2.山東師范大學(xué) 信息科學(xué)與工程學(xué)院,山東濟(jì)南 250014;3.大連理工大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,遼寧大連 116024)

0 引 言

本文考慮的圖,均指簡(jiǎn)單有限無向圖,其他未加說明的術(shù)語和記號(hào)參見文獻(xiàn)[1].圖G=(V(G),E(G)),其中V(G)和E(G)分別表示圖G的頂點(diǎn)集和邊集.誘導(dǎo)子圖〈G,S〉是以SV(G)為頂點(diǎn)集和G中端點(diǎn)均在S中的所有邊構(gòu)成的子圖.頂點(diǎn)v∈V(G)的閉鄰域N[v]={u∈V(G):vu∈E(G)}∪{v},相應(yīng)地,SV(G)的閉鄰域.獨(dú)立集SV(G)是由兩兩不相鄰的頂點(diǎn)構(gòu)成的集合,頂點(diǎn)獨(dú)立集大小的最大值稱為獨(dú)立數(shù),記做α(G).

路徑冪圖Pkn是指連接路徑圖Pn中所有距離不超過k的頂點(diǎn)對(duì)所得到的圖.當(dāng)n為不小于5的奇數(shù)時(shí),Flower Snark圖Fn=(V(Fn),E(Fn))被定義為4n個(gè)頂點(diǎn)的簡(jiǎn)單無向圖,其中V(Fn)={ui:0≤i≤n-1}∪{vi:0≤i≤n-1}∪{wi:0 ≤i≤2n-1},且.當(dāng)n=3或n為不小于4的偶數(shù)時(shí),Fn被稱為Flower Snark的相關(guān)圖.(1)取S={v(k+1)i:0≤(k+1)i≤n-1}V()(圖1示例了幾個(gè)路徑冪圖的獨(dú)立集),則S是路徑冪圖的一個(gè)獨(dú)立集并且|S|=n/(k+多錐圖是由一個(gè)長度為m的圈Cm以及l(fā)個(gè)孤立點(diǎn)組成的圖,其中每個(gè)孤立點(diǎn)都與Cm的所有點(diǎn)有邊關(guān)聯(lián),記做Wl,m.

圖的獨(dú)立數(shù)是圖論中最重要的參數(shù)之一,因而吸引了無數(shù)的研究者.這些研究多集中在討論一般圖的獨(dú)立數(shù)的上界和/或下界上[2～11],對(duì)于具體的某些特定的類圖,比如路徑冪圖、Flower Snark及其相關(guān)圖、多錐圖等類圖的獨(dú)立數(shù)問題則很少有文獻(xiàn)直接涉及.

本文研究路徑冪圖、Flower Snark圖及多錐圖的獨(dú)立數(shù)問題,并給出其獨(dú)立數(shù)的準(zhǔn)確值.

1 路徑冪圖的獨(dú)立數(shù)

在本章中討論路徑冪圖的獨(dú)立數(shù).

定理1 路徑冪圖的獨(dú)立數(shù)

證明 首先給出路徑冪圖Pkn的一個(gè)獨(dú)立集,使得然后證明從而得到定理的結(jié)論.于是

令S為路徑冪圖的任意一個(gè)獨(dú)立集,則由〈Pkn,V′(i,l)〉 ≌Kl,1 ≤l≤k+1, 可 得|S∩V′(i,l)|≤1.

設(shè)n=(k+1)m+t,則有;其中,當(dāng)t=0時(shí),ε=0,否則ε=1.于是,由S的任意性,可知

圖1 路徑冪圖的獨(dú)立集Fig.1 Some independent sets of

2 Flower Snark及其相關(guān)圖Fn的獨(dú)立數(shù)

對(duì)于n=3時(shí)Flower Snark相關(guān)圖的獨(dú)立數(shù)α(F3)=5留給讀者去驗(yàn)證.下面討論n≥4時(shí)Flow er Snark及其相關(guān)圖Fn的獨(dú)立數(shù).

定理2 Flower Snark圖Fn(n為不小于5的奇數(shù))的獨(dú)立數(shù)α(Fn)=2n-1.

證明 首先給出Flower Snark圖Fn的一個(gè)獨(dú)立集,使得 α(Fn)≥2n-1,然后證明α(Fn)≤2n-1,從而得到定理的結(jié)論,其中n為不小于5的奇數(shù).

(1)取S={u2i:0≤i≤(n-1)/2-1}∪{v2i+1:0≤i≤(n-1)/2-1}∪{vn-1}∪{w2i,wn+2i:0≤i≤(n-1)/2-1}V(Fn)(圖2示例了Flower Snark圖的獨(dú)立集),則S是 Flower Snark圖Fn的一個(gè)獨(dú)立集并且|S|=(n-1)/2+(n-1)/2+1+2 ×[(n-1)/2]=2n-1,于是 ,α(Fn)≥2n-1.

圖2 Flower Snark圖Fn的獨(dú)立集Fig.2 Independent set of Flower Snark graph Fn

(2)令S為Flower Snark圖Fn的任意一個(gè)獨(dú)立集,取x=|S∩{ui:0≤i≤n-1}|,y=|S∩{vi:0≤i≤n-1}|,z=|S∩{wi:0≤i≤2n-1}|.則|S|=x+y+z且得到如下整數(shù)規(guī)劃:

其中x,y,z∈N(N為自然數(shù)集).

由〈Fn,{ui:0≤i≤n-1}〉≌Cn得x≤(n-1)/2;

由〈Fn,{wi:0≤i≤2n-1}〉≌C2n得z≤n;

由x+y=|S∩{ui:0≤i≤n-1}|+|S∩{vi:0≤i≤n-1}|=|S∩{ui,vi:0≤i≤n-1}|及uivi∈E(Fn)得x+y≤n;

由z=|S∩{wi:0≤i≤2n-1}|≤|{wi:0≤i≤2n-1}-N[S∩{vi:0≤i≤n-1}]|=2n-2y得z≤2n-2y;

由|{vi:0≤i≤n-1}|=n得y≤n.

該整數(shù)規(guī)劃的最優(yōu)值為2n-1,于是|S|≤2n-1.又由S任意性,可知α(Fn)≤2n-1.

綜合(1)、(2),得Flower Snark圖Fn(n為不小于5的奇數(shù))的獨(dú)立數(shù)α(Fn)=2n-1.

定理3 Flower Snark相關(guān)圖Fn(n為不小于4的偶數(shù))的獨(dú)立數(shù)α(Fn)=2n.

證明 首先給出Flower Snark相關(guān)圖Fn的一個(gè)獨(dú)立集,使得α(Fn)≥2n,然后證明α(Fn)≤2n,從而得到定理的結(jié)論,其中n為不小于4的偶數(shù).

(1)取S={u2i:0≤i≤n/2-1}∪{v2i+1:0≤i≤n/2-1}∪{w2i,wn+2i:0≤i≤n/2-1}

V(Fn)(圖3示例了Flow er Snark相關(guān)圖的獨(dú)立集),則S是Flower Snark相關(guān)圖Fn的一個(gè)獨(dú)立集并且|S|=n/2+n/2+2×(n/2)=2n,于是 ,α(Fn)≥2n.

圖3 Flower Snark相關(guān)圖Fn的獨(dú)立集Fig.3 Independent set of Flower Snark related graph Fn

(2)令S為Flower Snark相關(guān)圖Fn的任意一個(gè)獨(dú)立集,取x=|S∩{ui,vi:0≤i≤n-1}|,y=|S∩{wi:0≤i≤2n-1}|,則|S|=x+y.

由uivi∈E(Fn)得x=|S∩{ui,vi:0≤i≤n-1}|≤n,由〈Fn,{wi:0≤i≤2n-1}〉 ≌C2n得y≤n,于是|S|=x+y≤n+n=2n.又由S任意性,可知 α(Fn)≤2n.

綜合(1)、(2),得Flower Snark相關(guān)圖Fn(n為不小于4的偶數(shù))的獨(dú)立數(shù)α(Fn)=2n.

3 多錐圖W l,m的獨(dú)立數(shù)

多錐圖是由一個(gè)長度為m的圈Cm以及l(fā)個(gè)孤立點(diǎn)組成的圖,其中每個(gè)孤立點(diǎn)都與Cm的所有

點(diǎn)有邊關(guān)聯(lián),記做Wl,m,即V(Wl,m)={ui:0≤i≤l-1}∪{vi:0≤i≤m-1}且E(Wl,m)={uivj:0≤i≤l-1,0≤j≤m-1}∪{viv(i+1)modm:0≤i≤m-1}.下面討論多錐圖Wl,m的獨(dú)立數(shù).

定理4 多錐圖Wl,m的獨(dú)立數(shù)α(Wl,m)=

證明 首先給出多錐圖Wl,m的獨(dú)立集,使得然后證明,從而得到定理的結(jié)論.

(1)當(dāng)l≥m/2時(shí),取S={ui:0≤i≤l-1}V(Wl,m),則S是Wl,m的一個(gè)獨(dú)立集且

(2)令S為多錐圖Wl,m的任意一個(gè)獨(dú)立集,取x=|S∩{ui:0≤i≤l-1}|,y=|S∩{vi:0≤i≤m-1}|,則|S|=x+y且x≤l.

由〈Wl,m,{vi:0≤i≤m-1}〉≌Cm可知.同時(shí),由{uivj:0≤i≤l-1,0≤j≤m-1}E(Wl,m)可知xy=0.于是有如下整數(shù)規(guī)劃:

其中x,y∈N(N為自然數(shù)集).

4 結(jié) 論

(1)路徑冪圖的獨(dú)立數(shù)

(2)Flower Snark圖Fn的獨(dú)立數(shù)α(Fn)=2n-1,n為不小于5的奇數(shù);

(3)Flower Snark相關(guān)圖Fn的獨(dú)立數(shù)α(Fn)=2n,n為不小于4的偶數(shù);

(4)多錐圖Wl,m的獨(dú)立數(shù)

[1]WEST D B.Introduction to Graph Theory[M].2nd ed.Englewood Cliffs:Prentice H all,2001

[2]GUO SG.On the spectral radius of unicyclic graphs w ithnvertices and edge independence numberq[J].Ars Combinatoria,2007,83:279-287

[3]KLAVZAR S.Some new bounds and exact resu lts on the independence number of Cartesian product graphs[J].Ars Combinatoria,2005,74:173-186

[4]MARTIN S P,POW ELL JS,RALL D F.On the independence number of the Cartesian product of caterpillars[J].Ars Combinatoria,2001,60:73-84

[5]PEPPER R.An upper bound on the independence number of benzenoid systems[J].Discrete App lied M athematics,2008,156(3):607-619

[6]李雨生,ROUSSEAU C C,臧文安.獨(dú)立數(shù)的一個(gè)下界[J].中國科學(xué)(A輯),2001,31(10):865-870

[7]LU M,LIU H Q,TIAN F.Lap lacian spectral bounds for clique and independence numbers of graphs[J].Journa l of Combinatorial Theory SeriesB,2007,97(5):726-732

[8]BERGER E,ZIV R.A note on the edge cover number and independence number in hypergraphs[J]. Discrete Mathematics, 2008, 308(12):2649-2654

[9]EGAWA Y,ENOMOTO H,JENDROL D.Independence number and vertex-disjoint cycles[J].Discrete M athematics,2007,307(11-12):1493-1498

[10]AM IN A T,HAK IM I S L.Upper bounds on the order of a clique of a graph[J].SIAM Journal of Applied Mathematics,1972,22(4):569-573

[11]徐保根.關(guān)于正則圖的獨(dú)立數(shù)的一點(diǎn)注記[J].華東交通大學(xué)學(xué)報(bào),1994,11(4):61-64