圈圖在張量積下的獨立數(shù)

李晨瑩

(浙江師范大學(xué)數(shù)理與信息工程學(xué)院, 浙江金華 321004)

圈圖在張量積下的獨立數(shù)

李晨瑩

(浙江師范大學(xué)數(shù)理與信息工程學(xué)院, 浙江金華 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)當(dāng)且僅當(dāng)|{i∶(ui,vi)∈Gi}|≥2.在本文中將證明， 當(dāng)G1,G2,G3均為圈圖時，等式α(G1,G2,G3)=max{α(G1)α(G2)|G3|,α(G1)α(G3)|G2|,α(G2)α(G3)|G1|}成立，并且還刻畫了其最大獨立集的結(jié)構(gòu).

EKR定理； 點傳遞； 本原性； 獨立數(shù)

1 引言及導(dǎo)語

令G和H兩個圖的直積圖G×H定義如下：

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

[(u1,u2),(v1,v2]∈E(G×H)當(dāng)且僅當(dāng)(u1,v1)∈G且(u2,v2)∈H.

顯然，當(dāng)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是規(guī)則的.如果G×H中的每一個極大獨立集都是規(guī)則的，那么我們稱G×H是MIS-正規(guī)的.1996年， Frankl[3]證明了等式(1)對Kneser圖是成立的.

定理1[3]設(shè)n1,n2,…,nk和r1,r2…rk是正整數(shù)，2ri≤ni,1≤i≤k.那么

在圖論中，圈圖Kn:r(2r≤n)的頂點集是[n]，頂點i和j之間無邊相連當(dāng)且僅當(dāng)|i-j|≤r或 |n-i+j|≤r.顯然圖α(Kn:r)=r. 2006年，Valencia-Pabon and Vera[5]得到了圈圖直積的獨立數(shù).

2002年，B.Larose和C.Tardif[4]分別確定了Kneser圖、圈圖做任意次直積后的獨立集結(jié)構(gòu).

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

定理3[5]設(shè)n1,n2,…,nk和r1,r2…rk是正整數(shù)，2ri≤ni,1≤i≤k.那么

2007年，Ku和Wong[6]研究了對稱群的獨立數(shù)和MIS-正規(guī)性質(zhì).

定理4[6]設(shè)n1,n2,…,nk是正整數(shù)，那么

并且直積Sn1×Sn2×…×Snk是MIS-正規(guī)的，除非存在i，j和l使得下面三種情況之一成立：

(1)ni=nj=nl=2;

(2)ni=nj=3;

(3)ni=2且nj=3.

Albertson and Collins[7]在1985年提出了非同態(tài)引理，它對確定點傳遞圖的獨立集的上界是十分有效的.

引理1[7]設(shè)G和H是兩個圖，如果G是點傳遞的并且存在一個同態(tài)映射φ:H→G，那么

在引理1中，取H為G一個誘導(dǎo)子圖，φ是從H到G的嵌入映射，我們會得到如下引理.

由引理2可以得到以下命題.為了引入這些結(jié)論，我們先介紹一些相關(guān)定義.

對A?V(G), 我們定義

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

引理3[9]如果G和H是兩個點傳遞圖，那么G×H是MIS-正規(guī)的并且是IS-非本原的，除非下列情況之一成立：

2011年， 張華軍確定了任意兩個點傳遞圖的直積圖的獨立數(shù)，并刻畫了其最大獨立集的結(jié)構(gòu)，完全解決了Tardif提出的問題.

最近，Taidif給出了三個點傳遞圖乘積的定義.假設(shè)圖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)當(dāng)且僅當(dāng)|{i:(ui,vi)∈Gi}|≥2.

如果G中的一個獨立集S能寫成A×B×C的形式，我們稱S是規(guī)則的.如果G中的每一個極大獨立集都是規(guī)則的，那么我們稱G是MIS-正規(guī)的.

顯然

α(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.在本文中我們將證明， 當(dāng)G1,G2,G3都是圈圖時這個等式成立，并且確定圈圖Kn:r在張量積定義下的獨立集結(jié)構(gòu).

圖1 (G1,G2,G3)

定理6 設(shè)ni,ri是正整數(shù)且2ri≤ni,令Gi=Kni:ri(1≤i≤3), 那么等式

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

2 定理6的證明

設(shè)G=(G1,G2,G3)，Gi=Kni:ri，I(Gi)是Gi的最大獨立集，并且I是G的最大獨立集.在證明定理6之前我們先引入文獻[12]中的一個結(jié)論.

引理4[12]設(shè)n，r是正整數(shù)且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)|+

因此我們可以得到以下結(jié)論.

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.因此假設(shè)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的一個獨立集.

假設(shè)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是最大的整數(shù)使得對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的一個獨立集.假設(shè)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).設(shè)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可知，當(dāng)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 假設(shè)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).假設(shè)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)都是規(guī)則的.如果G不是MIS-正規(guī)的，那么一定存在一個最大獨立集I使得Δi(I)是規(guī)則的但I不是規(guī)則的，其中i∈[3].由對稱性不妨設(shè)i=1.如果Δi(I)=V(G1)×S×T，那么由定義可知I=V(G1)×S×T，從而I是規(guī)則的.因此Δ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—)， 女， 浙江麗水人， 在讀碩士生. 研究方向： 圖論.

[責(zé)任編輯 胡廷鋒]