李晨莹
(浙江师范大学数理与信息工程学院, 浙江金华 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定理; 点传递; 本原性; 独立数
令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可以得到以下命……


