路径幂图、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