圈图在张量积下的独立数

2017-12-22 07:16:27李晨莹
洛阳师范学院学报 2017年11期
关键词:定义规则

李晨莹

(浙江师范大学数理与信息工程学院, 浙江金华 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可以得到以下命……

登录APP查看全文

猜你喜欢
定义规则
撑竿跳规则的制定
数独的规则和演变
永远不要用“起点”定义自己
海峡姐妹(2020年9期)2021-01-04 01:35:44
定义“风格”
规则的正确打开方式
幸福(2018年33期)2018-12-05 05:22:42
让规则不规则
Coco薇(2017年11期)2018-01-03 20:59:57
TPP反腐败规则对我国的启示
搜索新规则
成功的定义
山东青年(2016年1期)2016-02-28 14:25:25
修辞学的重大定义
当代修辞学(2014年3期)2014-01-21 02:30:44