路徑冪圖、Flower Snark圖及多錐圖獨立數

徐連誠, 楊元生, 夏尊銓

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

0 引 言

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

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

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

本文研究路徑冪圖、Flower Snark圖及多錐圖的獨立數問題,并給出其獨立數的準確值.

1 路徑冪圖的獨立數

在本章中討論路徑冪圖的獨立數.

定理1 路徑冪圖的獨立數

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

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

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

圖1 路徑冪圖的獨立集Fig.1 Some independent sets of

2 Flower Snark及其相關圖Fn的獨立數

對于n=3時Flower Snark相關圖的獨立數α(F3)=5留給讀者去驗證.下面討論n≥4時Flow er Snark及其相關圖Fn的獨立數.

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

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

(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圖的獨立集),則S是 Flower Snark圖Fn的一個獨立集并且|S|=(n-1)/2+(n-1)/2+1+2 ×[(n-1)/2]=2n-1,于是 ,α(Fn)≥2n-1.

圖2 Flower Snark圖Fn的獨立集Fig.2 Independent set of Flower Snark graph Fn

(2)令S為Flower Snark圖Fn的任意一個獨立集,取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且得到如下整數規劃:

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

由〈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.

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

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

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

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

(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相關圖的獨立集),則S是Flower Snark相關圖Fn的一個獨立集并且|S|=n/2+n/2+2×(n/2)=2n,于是 ,α(Fn)≥2n.

圖3 Flower Snark相關圖Fn的獨立集Fig.3 Independent set of Flower Snark related graph Fn

(2)令S為Flower Snark相關圖Fn的任意一個獨立集,取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相關圖Fn(n為不小于4的偶數)的獨立數α(Fn)=2n.

3 多錐圖W l,m的獨立數

多錐圖是由一個長度為m的圈Cm以及l個孤立點組成的圖,其中每個孤立點都與Cm的所有

點有邊關聯,記做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的獨立數.

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

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

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

(2)令S為多錐圖Wl,m的任意一個獨立集,取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可知.同時,由{uivj:0≤i≤l-1,0≤j≤m-1}E(Wl,m)可知xy=0.于是有如下整數規劃:

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

4 結 論

(1)路徑冪圖的獨立數

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

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

(4)多錐圖Wl,m的獨立數

[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,臧文安.獨立數的一個下界[J].中國科學(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]徐保根.關于正則圖的獨立數的一點注記[J].華東交通大學學報,1994,11(4):61-64