茍小麗

(蘭州交通大學(xué) 數(shù)理學(xué)院，甘肅 蘭州 730070)

0 引言

本文所考慮的圖均為簡(jiǎn)單無向圖.設(shè)圖G的頂點(diǎn)集為V(G)={1,2,…,n},它的鄰接矩陣為A=(aij)n×n,其中當(dāng)頂點(diǎn)i和j相鄰時(shí),aij=1; 否則aij=0.圖G的特征值是其鄰接矩陣的特征值.

設(shè)A(G)的互異特征值為λ1>λ2>…>λk,且它們的重?cái)?shù)分別為m(λ1),m(λ2),…,m(λk),則圖G的譜記為

一個(gè)有限k-正則圖G稱為Ramanujan圖[1],如果

其中：λ(G)為G的不同于±k的特征值絕對(duì)值的最大值.關(guān)于Ramanujan圖及相關(guān)擴(kuò)展圖的研究, 可參考文獻(xiàn)[2-8].

1878年，A Cayley 為解釋群的生成元和定義關(guān)系首次提出凱萊圖的概念.1992年, Resmini 和 Jungnickel[9]定義了雙凱萊圖.

設(shè)H是一個(gè)具有單位元1H的群,R,L,S是H的子集,且1H?R=R-1,1H?L=L-1,則H上的雙凱萊圖BC(H;R,L,S)是指以H×{0,1}為頂點(diǎn)集的無向圖,且(h,i)和(g,j)相鄰,當(dāng)且僅當(dāng)以下條件之一成立:

(i)i=j=0且gh-1∈R;

(ii)i=j=1且gh-1∈L;

(iii)i=0,j=1且gh-1∈S.

特別地,若S由H的單位元構(gòu)成, Kovács 等[10]稱其為H上的一-匹配雙凱萊圖.

關(guān)于(一-匹配)雙凱萊圖的一些組合性質(zhì)和代數(shù)性質(zhì),其中包括弧傳遞性、強(qiáng)正則性、自同構(gòu)和點(diǎn)傳遞性,可參考文獻(xiàn)[9-12].

設(shè)R是有單位元1≠0的有限交換環(huán),R×表示其單位的集合.局部環(huán)是有唯一極大理想的交換環(huán)[13].由文獻(xiàn)[13-14]可知,若R是具有唯一極大理想M的局部環(huán),則R×=RM.每個(gè)有限交換環(huán)可表示為有限局部環(huán)的乘積,且這種分解在不計(jì)此類局部環(huán)的排列次序時(shí)是唯一的.因此,后續(xù)討論總是基于以下假設(shè).

假設(shè)1[4]R=R1×R2×…×Rs是具有單位元1≠0的有限交換環(huán),其中Ri是具有mi階極大理想Mi的局部環(huán).設(shè)

|R1|/m1≤|R2|/m2≤…≤|Rs|/ms.

顯然,

(1)

定義1[5]給定一個(gè)交換環(huán)R,R上的二次單位凱萊圖GR定義為R關(guān)于TR=QR∪(-QR)在加法群上的凱萊圖Cay(R，TR),其中QR={u2:u∈R×},即GR有頂點(diǎn)集R,使得x,y∈R相鄰,當(dāng)且僅當(dāng)x-y∈TR.

這個(gè)概念是Zn上的二次單位凱萊圖GZn的推廣[15], 當(dāng)n≡1(mod 4)且為素?cái)?shù)時(shí), GZn是n階Paley圖.隨著對(duì)GZn結(jié)構(gòu)性質(zhì)的進(jìn)一步研究,de Beaudrap將GZn在n的素因子上分解為張量積, 還計(jì)算了GZn的直徑, 并給出GZn是完美的條件[15].

文獻(xiàn)[16]基于單位凱萊圖的概念定義了單位一-匹配雙凱萊圖.本文類比單位一-匹配雙凱萊圖的概念, 在二次單位凱萊圖的基礎(chǔ)上定義了二次單位一-匹配雙凱萊圖的概念.

定義2給定一個(gè)交換環(huán)R,R上的二次單位一-匹配雙凱萊圖GR定義為R加法群上的一-匹配雙凱萊圖BC(R;TR,TR,{0}),其中TR=QR∪(-QR),QR={u2:u∈R×}.

2015年,劉曉剛等[5]給出了二次單位凱萊圖是 Ramanujan 圖的等價(jià)刻畫.受此啟發(fā),本文主要討論了二次單位一-匹配雙凱萊圖是 Ramanujan 圖的等價(jià)條件.

1 二次單位一-匹配雙凱萊圖

兩個(gè)圖G和H的笛卡爾積記作G□H,其頂點(diǎn)集為V(G)×V(H),頂點(diǎn)(u,v)和(x,y)相鄰當(dāng)且僅當(dāng)v=y且u和x在G中相鄰,或u=x且v和y在H中相鄰.

引理1[17]設(shè)G和H是兩個(gè)圖,其特征值分別為λ1,λ2,…,λn和μ1,μ2,…,μm,則G和H的特征值為λi+μj,1≤i≤n,1≤j≤m.

引理2[5]設(shè)R是具有m階極大理想M的局部環(huán),則

(1)若|R|/m≡1(mod 4),則

(2)若|R|/m≡3(mod 4),則

Spec(GR)=

根據(jù)二次單位一-匹配雙凱萊圖和笛卡爾積的定義,有GR?Cay(R,TR)□P2=GR□P2,其中P2為2長(zhǎng)路.由引理1和2可得如下結(jié)論.

定理1設(shè)R是具有m階唯一極大理想M的局部環(huán),則

(1)若|R|/m≡1(mod 4),則

(2)若|R|/m≡3(mod 4),則

Spec(GR)=

引理3[5]設(shè)R如假設(shè)1所示,則GR=GR1?GR2?…?GRs當(dāng)且僅當(dāng)至多存在一個(gè)Rj,使得-1?QRj.

定理2設(shè)R如假設(shè)1所示,|Ri|/mi≡1(mod 4),1≤i≤s,則

GR=(GR1?GR2?…?GRs)□P2.

證明根據(jù)二次單位一-匹配雙凱萊圖和笛卡爾積的定義,有

GR?Cay(R,TR)□P2=GR□P2,

其中P2為2長(zhǎng)路.因?yàn)閨Ri|/mi≡1(mod 4),1≤i≤s,所以-1∈QRi/Mi,1≤i≤s,于是-1∈QRi,1≤i≤s,從而由引理3可知,

GR=GR1?GR2?…?GRs,

故GR=(GR1?GR2?…?GRs)□P2.

令

λA,B=(-1)|B|·

其中，A,B為{1,2,…,s}的不交子集[5].特別地,λ?，?=|R×|/2s.

引理4[5]設(shè)R如假設(shè)1所示,|Ri|/mi≡1(mod 4),1≤i≤s,則GR的特征值為

(1)λA,B,重?cái)?shù)為

其中,所有的(A,B)對(duì)均為{1,2,…,s}的子集,且A∩B=?;

(2)0，重?cái)?shù)為

|R|-

由引理1, 定理2和引理4可得:

定理3設(shè)R如假設(shè)1所示,|Ri|/mi≡1(mod 4),1≤i≤s,則GR的特征值為

(1)λA,B±1,重?cái)?shù)為

其中,所有的(A,B)對(duì)均為{1,2,…,s}的子集,且A∩B=?;

(2)±1,重?cái)?shù)為

|R|-

引理5[5]設(shè)R如假設(shè)1所示,|Ri|/mi≡1(mod 4),1≤i≤s,R0是具有m0階極大理想M0的局部環(huán),且|R0|/m0≡3(mod 4),則GR0×R的特征值為

其中,所有的(A,B)對(duì)均為{1,2,…,s}的子集,且A∩B=?;

其中,所有的(A,B)對(duì)均為{1,2,…,s}的子集,且A∩B=?;

(3)0,重?cái)?shù)為

|R|-

由引理1, 定理2和引理5可得：

定理4設(shè)R如假設(shè)1所示,|Ri|/mi≡1(mod 4),1≤i≤s,R0是具有m0階極大理想M0的局部環(huán),且|R0|/m0≡3(mod 4),則GR0×R的特征值為

其中,所有的(A,B)對(duì)均為{1,2,…,s}的子集，且A∩B=?;

其中,所有的(A,B)對(duì)均為{1,2,…,s}的子集,且A∩B=?;

(3)±1,重?cái)?shù)為

|R|-

推論1(1)若p≡1(mod 4)為素?cái)?shù),且α≥1為整數(shù),則

Spec(GZpα)=

(2)若p≡3(mod 4)為素?cái)?shù),且α≥1為整數(shù),則

Spec(GZpα)=

(1)

(2)±1,重?cái)?shù)為

(1)

(2)

(-1)|B|+1·

重?cái)?shù)為

其中所有的(A,B)對(duì)均為{1,2,…,s}的子集,且A∩B=?;

(3)±1,重?cái)?shù)為

2 Ramanujan二次單位一-匹配雙凱萊圖

引理6[18]設(shè)R是具有m階唯一極大理想的有限局部環(huán),則存在素?cái)?shù)p使得|R|,m和|R|/m都是p的冪次.

定理5設(shè)R如假設(shè)1所示,|Ri|/mi≡1(mod 4),1≤i≤s,R0是具有m0階極大理想M0的局部環(huán),且|R0|/m0≡3(mod 4),則

(1)GR0是Ramanujan圖,當(dāng)且僅當(dāng)

(2)GR是Ramanujan圖,當(dāng)且僅當(dāng)R?Fq,其中q≡1(mod 4)為素?cái)?shù)的冪;

(3)GR0×R是Ramanujan圖,當(dāng)且僅當(dāng)

R0×R?F3×F9.

證明由文獻(xiàn)[5]可知,GR0的正則度為|R0×|=|R0|-m0,GR的正則度為|R×|/2s,GR0×R的正則度為|R0×||R×|/2s.則由引理1和定理2可知,GR0的正則度為|R0|-m0+1,GR的正則度為|R×|/2s+1,GR0×R的正則度為|R0×||R×|/2s+1.

(1)根據(jù)定理1(2),當(dāng)|R0|-m0-1≥m0+1,即|R0|≥2m0+2時(shí),GR0是Ramanujan圖

當(dāng)|R0|-m0-1≤m0+1,即|R0|≤2m0+2時(shí),GR0是Ramanujan圖

(2)根據(jù)定理3,GR是Ramanujan圖

λA,B±1≠±(|R×|/2s+1).

因?yàn)閨λA,B±1|≤|λA,B|+1≤|λ?，{1}|+1≠|(zhì)R×|/2s+1,所以GR是Ramanujan圖

(2)

(3)

又因?yàn)?/p>

則當(dāng)s≥4時(shí),由式(1)可知,

|R×|/2s≥

即式(3)不成立,所以GR不是Ramanujan圖.

下面考慮1≤s≤3的情況.

情形1s=1.

若m1≥8時(shí),以上不等式不成立,所以GR不是Ramanujan圖.

假設(shè)m1≤7,因?yàn)閨R1|/m1≡1(mod 4),所以由引理6可知,m1=1,3,5或7.

由文獻(xiàn)[19]可知, 具有素?cái)?shù)階p的極大理想的有限交換局部環(huán)是Zp2和Zp[X]/(X2),它們的剩余域均為Zp,又由|R1|/m1≡1(mod 4)可知m1=1或5.

當(dāng)m1=1時(shí),R1?Fq，q≡1(mod 4)為素?cái)?shù)的冪.根據(jù)式(2),所以GFq是Ramanujan圖.

當(dāng)m1=5時(shí),R1?Z25或Z5[X]/(X2).此時(shí)式(2)不成立,所以GR不是Ramanujan圖.

情形2s=2.

此時(shí),式(3)等價(jià)于

若m1m2≥4或|R2|/m2≥17,則以上不等式不成立,所以GR不是Ramanujan圖.

假設(shè)m1m2≤3,|R2|/m2≤16.

因?yàn)閨Ri|/mi≡1(mod 4),i=1,2,所以由引理6可知m1m2=1或m1m2=3.注意到,Z9和Z3[X]/(X2)是恰有3個(gè)元素的唯一極大理想的局部環(huán),它們的剩余域均為Z3,這與|Ri|/mi≡1(mod 4),i=1,2矛盾,所以m1m2=3不可能出現(xiàn),因此m1m2=1,且以下條件之一將會(huì)出現(xiàn):

(Ⅰ)R1?R2?F5;

(Ⅱ)R1?R2?F9;

(Ⅲ)R1?R2?F13;

(Ⅳ)R1?F5，R2?F9;

(Ⅴ)R1?F5，R2?F13;

(Ⅵ)R1?F9，R2?F13.

將其依次代入式(2),式(2)均不成立,所以GR不是Ramanujan圖.

情形3s=3.

此時(shí),式(3)等價(jià)于

因?yàn)閨Ri|/mi≡1(mod 4).i=1,2,3,所以R1?R2?R3?F5,此時(shí)式(2)不成立,所以GR不是Ramanujan圖.

(3)令

|λ|=

由定理4可知,GR0×R是Ramanujan圖

設(shè)

μA,B=

此時(shí),GR0×R是Ramanujan圖

(4)

因?yàn)?/p>

所以式(4)不成立,除非

(5)

又因?yàn)?/p>

所以當(dāng)s≥3時(shí),由式(1)可知,

即式(5)不成立,所以GR0×R不是Ramanujan圖.

下面考慮1≤s≤2的情況.

子情形1.1s=1.

此時(shí),式(5)等價(jià)于

m0m1((|R0|/m0)-1)((|R1|/m1)-1)<

若m0m1≥4或|R0|/m0≥9,則以上不等式不成立,所以GR0×R不是Ramanujan圖.

假設(shè)m0m1≤3,|R0|/m0≤8.

由引理6可知m0m1=1或m0m1=3.又因?yàn)閨R0|/m0≡3(mod 4),|R1|/m1≡1(mod 4),所以m0=m1=1或m0=3,m1=1.

當(dāng)m0=m1=1時(shí),R0?F3或R0?F7.

R0×R1?F3×F5,F7×F5,

F7×F9,F7×F13,F7×F17,

F7×F25,F7×F29,F7×F37或F7×F41.

將其依次代入式(4)中,式(4)均不成立,所以GR0×R不是Ramanujan圖.

當(dāng)m0=3,m1=1時(shí),R0?Z9或Z3[X]/(X2).

子情形1.2s=2.

此時(shí),式(5)等價(jià)于

因?yàn)閨R0|/m0≡3(mod 4),|Ri|/mi≡1(mod 4),i=1,2,則R0?F3,R1?R2?F5,此時(shí)式(4)不成立,所以GR0×R不是Ramanujan圖.

此時(shí),GR0×R是Ramanujan圖

(6)

因?yàn)?/p>

所以式(6)不成立,除非

(7)

當(dāng)s≥3時(shí),由式(1)可知,

即式(7)不成立,所以GR0×R不是Ramanujan圖.

下面考慮1≤s≤2的情況.

子情形2.1s=1.

此時(shí),式(7)等價(jià)于

8((|R0|/m0)-1).

若m0m1≥3或|R1|/m1>49,則以上不等式不成立,所以GR0×R不是Ramanujan圖.

假設(shè)m0m1≤2,|R1|/m1≤49.

因?yàn)閨R0|/m0≡3(mod 4),|R1|/m1≡1(mod 4),則由引理6可知,m0=m1=1.于是

R1?F5,F9,F13,F17,F25,F29,F37,F41或F49,

R0×R1?F3×F9,F3×F13,F3×F17,

F3×F25,F3×F29,F3×F37,F3×F41,

F3×F49或F7×F49.

將其依次代入式(6)中,得GF3×F9是Ramanujan圖.

子情形2.2s=2.

此時(shí),式(7)等價(jià)于

4((|R0|/m0)-1)2.