圈圖在張量積下的獨立數

李晨瑩

(浙江師范大學數理與信息工程學院, 浙江金華 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可以得到以下命……