圈图在张量积下的独立数

李晨莹

(浙江师范大学数理与信息工程学院, 浙江金华 321004)

圈图在张量积下的独立数

李晨莹

(浙江师范大学数理与信息工程学院, 浙江金华 321004)

图G1，G2和G3的张量积(G1,G2,G3)定义为V(G1,G2,G3)=V(G1)×V(G2)×V(G3),[(u1,u2,u3),(v1,v2,v3)]∈E(G1,G2,G3)当且仅当|{i∶(ui,vi)∈Gi}|≥2.在本文中将证明， 当G1,G2,G3均为圈图时，等式α(G1,G2,G3)=max{α(G1)α(G2)|G3|,α(G1)α(G3)|G2|,α(G2)α(G3)|G1|}成立，并且还刻画了其最大独立集的结构.

EKR定理； 点传递； 本原性； 独立数

1 引言及导语

令G和H两个图的直积图G×H定义如下：

V(G×H)=V(G)×V(H),

[(u1,u2),(v1,v2]∈E(G×H)当且仅当(u1,v1)∈G且(u2,v2)∈H.

显然，当I是图G(或H)的一个独立集时，I×H(或G×I)是G×H的一个独立集， 从而α(G×H)≥max{α(G)|H|,α(H)|G|}．Jha和KLavžar[1]证明了这个不等式对某些非点传递图等号是不成立的.1998年，Tardif[2]提出了等式

α(G×H)=max{α(G)|H|,α(H)|G|}

(1)

是否对所有的点传递图G和H都成立的公开问题.如果G×H中的一个独立集S能写成A×B的形式，我们称S是规则的.如果G×H中的每一个极大独立集都是规则的，那么我们称G×H是MIS-正规的.1996年， Frankl[3]证明了等式(1)对Kneser图是成立的.

定理1[3]设n1,n2,…,nk和r1,r2…rk是正整数，2ri≤ni,1≤i≤k.那么

在图论中，圈图Kn:r(2r≤n)的顶点集是[n]，顶点i和j之间无边相连当且仅当|i-j|≤r或 |n-i+j|≤r.显然图α(Kn:r)=r. 2006年，Valencia-Pabon and Vera[5]得到了圈图直积的独立数.

2002年，B.Larose和C.Tardif[4]分别确定了Kneser图、圈图做任意次直积后的独立集结构.

定理2[4](1)Kk(r,n) (2r

定理3[5]设n1,n2,…,nk和r1,r2…rk是正整数，2ri≤ni,1≤i≤k.那么

2007年，Ku和Wong[6]研究了对称群的独立数和MIS-正规性质.

定理4[6]设n1,n2,…,nk是正整数，那么

并且直积Sn1×Sn2×…×Snk是MIS-正规的，除非存在i，j和l使得下面三种情况之一成立：

(1)ni=nj=nl=2;

(2)ni=nj=3;

(3)ni=2且nj=3.

Albertson and Collins[7]在1985年提出了非同态引理，它对确定点传递图的独立集的上界是十分有效的.

引理1[7]设G和H是两个图，如果G是点传递的并且存在一个同态映射φ:H→G，那么

在引理1中，取H为G一个诱导子图，φ是从H到G的嵌入映射，我们会得到如下引理.

由引理2可以得到以下命题.为了引入这些结论，我们先介绍一些相关定义.

对A⊆V(G), 我们定义

NG(A)={b∈V(G):(a,b)∈E(G)对某个a∈A成立}.

引理3[9]如果G和H是两个点传递图，那么G×H是MIS-正规的并且是IS-非本原的，除非下列情况之一成立：

2011年， 张华军确定了任意两个点传递图的直积图的独立数，并刻画了其最大独立集的结构，完全解决了Tardif提出的问题.

最近，Taidif给出了三个点传递图乘积的定义.假设图G1，G2和G3之间的顶点集互不相交，张量积(G1,G2,G3)定义为

V(G1,G2,G3)=V(G1)×V(G2)×V(G3),

[(u1,u2,u3),(v1,v2,v3)]∈E(G1,G2,G3)当且仅当|{i:(ui,vi)∈Gi}|≥2.

如果G中的一个独立集S能写成A×B×C的形式，我们称S是规则的.如果G中的每一个极大独立集都是规则的，那么我们称G是MIS-正规的.

显然

α(G1,G2,G3)≥max{α(G1)α(G2)|G3|,

α(G1)α(G3)|G2|,α(G2)α(G3)|G1|}.

一般情况而言，对于非点传递图这个等式不一定成立.例如图1(G1,G2,G3)中S={(x1,y1,z1),(x1,y1,z2),(x1,y1,z3),(x3,y1,z1),(x4,y1,z1),(x5,y1,z1),(x6,y1,z1)}是一个含有7个顶点的独立集，但是max{α(G1)α(G2)|G3|},α(G1)α(G3)|G2|,α(G2)α(G3)|G1|}=6<7.在本文中我们将证明， 当G1,G2,G3都是圈图时这个等式成立，并且确定圈图Kn:r在张量积定义下的独立集结构.

图1 (G1,G2,G3)

定理6 设ni,ri是正整数且2ri≤ni,令Gi=Kni:ri(1≤i≤3), 那么等式

α(G1,G2,G3)=max{r1r2n3,r1r3n2,r2r3n1}

2 定理6的证明

设G=(G1,G2,G3)，Gi=Kni:ri，I(Gi)是Gi的最大独立集，并且I是G的最大独立集.在证明定理6之前我们先引入文献[12]中的一个结论.

引理4[12]设n，r是正整数且2r≤n.对任意

我们考虑I到G1的投影∂: 对任意(i,x)∈V(G2)×V(G3)，∂(i,x)(I)={a∈G1:(a,i,x)∈I}.另外，对任意A⊆V(G2)×V(G3)，令∂A(I)=∪(i,x)∈A∂(i,x)(I).为叙述方便，我们将{(a,i,x):a∈A}记为A×{(i,x)}.

由引理4可以推出

|∂(i,x)(I)|+|∂(j,y)(I)|≤|∂(i,x)(I)|+

因此我们可以得到以下结论.

Claim: 对任意(i,x),(j,y)∈V(G2)×V(G3)，如果(i,j)∈E(G2)或(x,y)∈E(G3)，那么有|∂(i,x)(I)|+|∂(j,y)(I)|≤2r1.

定义

接下来我们通过给出三个引理来完成定理6的证明.

引理5 如果I是G的一个最大独立集，那么Δ1(I)也是G的一个最大的独立集.

证明 令

D1={(i,x)∈V(G2)×V(G3):|∂(i,x)(I)|=n1}

(2)

D2={(i,x)∈V(G2)×V(G3):r1<|∂(i,x)(I)|

(3)

D3={(i,x)∈V(G2)×V(G3):0<|∂(i,x)(I)|≤r1}

(4)

则

Δ1(I)={G1×{(i,x)}:(i,x)∈D1}∪

{I(G1)×{(i,x)}:(i,x)∈D2∪D3}

如果D2∪D3=φ，那么Δ1(I)=G1×{(i,x)}=∂(i,x)(I)×{(i,x)}=I.因此假设D2∪D3≠φ.

对任意的(i,x),(j,y)∈D1∪D2，由Claim可知，(i,j)∉E(G2)且(x,y)∉E(G3).另外，对任意(i,x),(j,y)∈D2∪D3，由定义可知(i,j)∉E(G2)或(x,y)∉E(G3)，否则与I是G的一个独立集相矛盾.因此,Δ1(I)是G的一个独立集.

假设D2=φ.对任意(i,x)∈D2，由定义知G1×{(i,x)}I.如果对任意(j,y)∈D3(i,j)∉E(G2)和(x,y)∉E(G3) 都成立，那么I′=I∪G1×{(i,x)}也是G的一个独立集，并且|I′|>|I|，从而与I的极大性相矛盾.因此，对任意的(i,x)∈D2，都存在(j,y)∈D3使得(i,j)∈E(G2)或(x,y)∈E(G3).令t是最大的整数使得对D2的任意非空子集D，只要|D|≤t时，就有|ND3(D2)|≥|D|.接下来我们证明t=|D2|.如果t<|D2|，那么D2存在一点(i,x)和一个t元子集D满足|ND3(D)|=t=|ND3(D∪ {(i,x)})|.令D′=D∪ {(i,x)}.已知是一个独立集，并且⊆

∂(i,x)(I)×{(i,x)}].因此，

也是G的一个独立集.假设D' ={(i1,x1),(i2,x2)…(it + 1,xt + 1) .由Hall匹配定理，我们可以重新排列ND3(D′)中的元素为ND3(D')={(j1,y1),(j2,y2)…(jt,yt)} ，使得对任意的1≤k≤t都有(ik,jk)∈E(G2)或(xk,yk)∈E(G3).由Claim我们可得出2r1≥|∂(i,x)(I)|+|∂(j,y)(I)|.并且由D′的定义，|∂(it+1,xt+1)(I)|

|∂(ik,xk)(I)|-|∂(jk,yk)(I)|)+

(n1-|∂(it+1,xt+1)(I)|)>0,

这与|I|的极大性相矛盾，因此|D2|=t.令D2={ (i1,x1),(i2,x2)…(it,xt)} ，存在(j1,y1),(j2,y2)…(jt,yt)∈ND3(D2)，使得对任意1≤k≤t都有(ik,jk)∈E(G2)或(xk,yk)∈E(G3).设ND3(D2) ={ (j1,y1),(j2,y2)…(js,ys)} ,D'3=D-{ (j1,y1),(j2,y2)…(jt,yt)} ,如果|ND3(D2)|>t，那么

显然，|∂(i,x)(I)|=n1对任意(i,x)∈D1都成立，并且由Claim可知，当k=1,2,…,t都有|∂(ik,xk)(I)|+|∂(jk,yk)(I)|≤2r1成立.而由|ND3(D2)|>|D2|可得，存在一个(ik,xk)或(j0,y0)使得(ik,j0)∈E(G2)或(xk,y0)∈E(G3)，因此由Claim我们可以推出2r1≥|∂(j0,y0)(I)|+|∂(ik,xk)(I)|.然而，由定义|∂(ik,xk)(I)|>r1可得r1>|∂(j0,y0)(I)|，因此可推出|Δ1(I)|>|I|，但这又与|I|的极大性相矛盾，所以|ND3(D2)|=|D2|=t.

类似的我们可以定义Δ2和Δ3，同理可证Δ2和Δ3也是G的一个最大独立集.

引理6 假设I是G中的任意一个最大独立集，那么Δ3Δ2Δ1(I)=V(G1)×I(G2)×I(G3) 或I(G1)×V(G2)×I(G3)或I(G1)×I(G2)×V(G3).

证明 由引理5知Δ2Δ1(I)也是G的一个最大独立集.不难验证存在A,B⊆V(G3)使得Δ2Δ1(I)=V(G1)×I(G2)×A∪I(G1)×I(G2)×B或I(G1)×V(G2)×A∪I(G1)×I(G2)×B.如果A=∅或B=∅，由定义和I的极大性可知Δ3Δ2Δ1(I)=V(G1)×I(G2)×I(G3)或I(G1)×V(G2)×I(G3)或I(G1)×I(G2)×V(G3).假设A≠φ和B≠φ.那么I=[V(G1)I(G1)]×I(G2)×A∪I(G1)×I(G2)×(A∪B)或I(G1)×[V(G2)I(G2)]×A∪I(G1)×I(G2)×(A∪B).显然A∪BV(G3)，否则与I是G中的独立集相矛盾.从而由定义知Δ3Δ2Δ1(I)=V(G1)×I(G2)×I(G3)或I(G1)×V(G2)×I(G3).引理得证.

对G的任意极大独立集I，显然|I|≥max{r1r2n3,r1r3n2,r2r3n1}.又由引理5和6知，|I|≤max{r1r2n3,r1r3n2,r2r3n1}.

从而

|I|=max{r1r2n3,r1r3n2,r2r3n1}.

因此

α(G1,G2,G3)=max{r1r2n3,r1r3n2,r2r3n1}.

证明 对G的任意一个最大独立集I.由引理6知，Δ3Δ2Δ1(I)都是规则的.如果G不是MIS-正规的，那么一定存在一个最大独立集I使得Δi(I)是规则的但I不是规则的，其中i∈[3].由对称性不妨设i=1.如果Δi(I)=V(G1)×S×T，那么由定义可知I=V(G1)×S×T，从而I是规则的.因此Δ1(I)=I(G1)×S×V(G3)或I(G1)×V(G2)×T.

[1] Jha P K, Klavzar S.Independence in direct-product graphs[J].Ars Combin，1998， 50： 53-60.

[2] Tardif C. Graph products and the chromatic difference sequence of vertex-transitive graphs[J]. Discrete Math， 1998， 185： 193-200.

[3] P.Frankl, An Erdos-Ko-Rado Theorem for direct products[J]. European J Combin, 1996， 17： 727-730.

[4] Larose B， Tardif C. Projectivity and independent sets in powers of graph[J].J. Graph Theory, 2002， 40： 162-171.

[5] Valencia-Pabon, M, Juan V. Independence and coloring properties of direct products of some vertex-transitive graphs[J]. Discrete Math, 2006， 306： 2275-2281.

[6] Ku C Y, Wong T W H. Intersecting families in the alternating group and direct product of systeric groups[J]. Electron.J Combin,2007， 14： R25.

[7] Albertson M O, Collins K L. Homomorphisms of 3-chromatic graphs[J]. Discrete Math, 1985， 54： 127-132.

[8] Cameron P J, Ku C Y. Intersecting families of permutations[J]. European J. Combin, 2003， 24： 881-890.

[9] Zhang H J. Primitivity and independent sets in direct products of vertex-transitive graphs J[J]. Graph Theory, 2011，67： 218-225.

[10] Zhang H J. Independent sets in direct products of vertex-transitive graphs[J]. J Combin Theory Ser B， 2012，102： 832-838.

[11] Wang J， Zhang H J. Intersecting families in a subset of boolean lattices[J]. Electron J Combin, 2011.

[12] Geng X B， Wang J， Zhang H J. Structure of independent sets in direct products of some vertex-transitive graphs[J] , 2012， 28(4)： 697-70.

Independent Number of Cycle Graph under Tensor Product

LI Chen-ying

(College of Mathematics and Information Engineering, Zhejiang Normal University, Jinhua 321004, China)

Tensor products (G1,G2,G3) of graphsG1,G2, andG3are defined asV(G1,G2,G3)=V(G1)×V(G2)×V(G3)[(u1,u2,u3),(v1,v2,v3)]∈E(G1,G2,G3) when and only when |{i:(ui,vi) ∈Gi}|≥2. This paper demonstrates whenG1,G2, andG3are cycle graphs, equationα(G1,G2,G3)=max{α(G1)α(G2)|G3|,α(G1)α(G3)|G2|,α(G2)α(G3)|G1|}can be established, and depicts the structure of its maximum independent set.

EKR theorem; vertex-transitive; primitivity; independent number

O157.5

A

1009-4970(2017)11-0008-05

2017-07-02

李晨莹(1984—)， 女， 浙江丽水人， 在读硕士生. 研究方向： 图论.

[责任编辑 胡廷锋]