有限交換環(huán)上的廣義單位Cayley圖的進(jìn)一步研究

熊騰飛，簡國明（.韶關(guān)學(xué)院 信息科學(xué)與工程學(xué)院；.韶關(guān)學(xué)院 數(shù)學(xué)與統(tǒng)計(jì)學(xué)院，廣東韶關(guān)5005）

有限交換環(huán)上的廣義單位Cayley圖的進(jìn)一步研究

熊騰飛1，簡國明2
（1.韶關(guān)學(xué)院 信息科學(xué)與工程學(xué)院；2.韶關(guān)學(xué)院 數(shù)學(xué)與統(tǒng)計(jì)學(xué)院，廣東韶關(guān)512005）

摘要：設(shè)R是一個(gè)含有非零單位元的有限交換環(huán),U(R)是R的單位群,G是U(R)的一個(gè)乘法子群,S是G的一個(gè)非空子集并且S-1={s-1|s∈S}?S.在研究廣義單位Cayley圖Γ(R,G,S)的若干性質(zhì)的基礎(chǔ)上，對(duì)當(dāng)S={s}時(shí),Γ(R,U(R), S)的性質(zhì)作進(jìn)一步研究，考察Γ(R,U(R),S)的同構(gòu)問題，得出Γ(R,U(R),S)的團(tuán)數(shù)和頂點(diǎn)著色數(shù),確定Γ(R,U(R),S)是完美圖的條件.

關(guān)鍵詞：單位Cayley圖;團(tuán)數(shù)；頂點(diǎn)著色數(shù);完美圖

單位Cayley圖是近年來的一個(gè)熱門研究領(lǐng)域,它們內(nèi)涵豐富,很好地把圖論和代數(shù)系統(tǒng)的研究結(jié)合起來,提供了研究代數(shù)問題的一種新方法.

設(shè)n＞1是一個(gè)正整數(shù),Zn即模n剩余類環(huán),許多學(xué)者對(duì)Zn上的單位Cayley圖進(jìn)行了研究,其中文獻(xiàn)［1-2］得到了許多很好的結(jié)論.2009年,R.Akhtar,M.Boggess等學(xué)者提出了一般的有限交換環(huán)上單位的Cayley圖GR的定義:設(shè)R是一個(gè)含有非零單位元的有限交換環(huán),U(R)為R的單位群,GR的頂點(diǎn)集是R,頂點(diǎn)x和y相鄰當(dāng)且僅當(dāng)x-y∈U(R).討論了GR的直徑、圍長、自同構(gòu)群、點(diǎn)連通度、邊連通度、團(tuán)數(shù)、著色數(shù)、邊著色數(shù),而且還解決了GR的平面性和完美性等問題［3］.在此之后,許多專家對(duì)環(huán)上的單位Cayley圖的性質(zhì)產(chǎn)生了濃厚的興趣,文獻(xiàn)［4-5］得出的一系列成果,使得該領(lǐng)域的成果豐富起來.

在N.Ashrafi等學(xué)者提出了一般環(huán)上的單位圖的概念以后［6］,K.Khashyarmanesh和M.R.Khorsandi推廣了單位Cayley圖的概念［7］:設(shè)R是一個(gè)含有非零單位元的有限交換環(huán),U(R)是R的單位群,G是U(R)的一個(gè)乘法子群,S是G的一個(gè)非空子集并且S-1={s-1|s∈S}?S,定義廣義單位Cayley圖Γ(R,G,S)的頂點(diǎn)集為R,頂點(diǎn)x與y相鄰當(dāng)且僅當(dāng)存在s∈S,使得x+sy∈G.當(dāng)G=U(R)時(shí),Γ(R,G,{-1})即單位Cayley圖,而Γ(R, G,{-1})就是單位圖.文獻(xiàn)［3，6-7］的一些結(jié)論推廣到Γ(R,G,S)中,很好地把環(huán)上的單位Cayley圖和單位圖統(tǒng)一了起來,范圍更加寬廣,內(nèi)涵更加豐富.

本文所指的圖都是簡單圖,即沒有自環(huán)和重邊的圖.設(shè)G是一個(gè)圖,V(G)表示圖G的頂點(diǎn)集;設(shè)a,b∈V(G), 若a,b是一條邊的兩個(gè)端點(diǎn),則稱a與b是相鄰的.獨(dú)立集指的是圖中兩兩不相鄰的頂點(diǎn)所組成的集合.圖G稱為二部圖,如果V(G),是兩個(gè)互不相交的獨(dú)立集的并集,這兩個(gè)獨(dú)立集稱為圖G的部集.

文獻(xiàn)［1］確定了當(dāng)S={s}時(shí),廣義單位Cayley圖Γ(R,G,S)的正則性,Γ(R,U(R),S)中任意兩點(diǎn)的公共鄰接點(diǎn)個(gè)數(shù)以及邊著色數(shù).本文主要對(duì)Γ(R,U(R),S)的性質(zhì)作進(jìn)一步研究,考察當(dāng)S={s}時(shí),Γ(R,U(R),{1})與Γ(R,U (R),{-1})的同構(gòu)問題,計(jì)算Γ(R,U(R),S)的團(tuán)數(shù)和頂點(diǎn)著色數(shù)，確定Γ(R,U(R),S)是完美圖的條件.

1　定義及引理

定義1稱一個(gè)圖是完美的,如果它的任意一個(gè)誘導(dǎo)子圖H,都有χ(H)=ω(H),其中χ(H)和ω(H)分別表示H的頂點(diǎn)著色數(shù)和團(tuán)數(shù)［8］.

定義2圖G中長度不小于5并且是奇數(shù)的誘導(dǎo)圈稱為奇洞［2］.

引理1設(shè)R是一個(gè)含單位元的交換環(huán).若R是Artin環(huán),則R可以表示成有限個(gè)Artin局部環(huán)的直和:( Ri為Artin局部環(huán)).如果又有(Ri為Artin局部環(huán)),則t=t,并且有{1,2,…,t}的一個(gè)置換σ,使得

引理2設(shè)R是一個(gè)有限環(huán),則1+1∈U(R)當(dāng)且僅當(dāng)|R|是奇數(shù).

引理3設(shè)R是一個(gè)含非零單位元的交換環(huán),J(R)是R的Jacobson根,G(R)表示環(huán)R上的單位圖.若x,y∈R,則：

（1）若x+J(R)和y+J(R)在圖G(R/J(R))中相鄰,則x+J(R)中的每一個(gè)元都與y+J(R)的任何一個(gè)元在G(R)中相鄰;

（2）若(1+1)·x∈U(R),則x+J(R)是G(R)中的一個(gè)團(tuán)［6］.

引理4設(shè)R是一個(gè)含單位元的交換環(huán),M是R的一個(gè)極大理想且|R/M|=2,則圖Γ(R,U(R),S)是一個(gè)二部圖［7］.

引理5設(shè)R是一個(gè)含非零單位元的有限交換環(huán),J(R)是R的Jacobson根.若S={s},1+s∈J(R),則Γ (R,U(R),S)?Γ(R,U(R),(-1)).

證由引理1,設(shè)是局部環(huán),其極大理想為Mi,i=1,2,…,t.設(shè)s=(s1,s2,…,st),則1+s=(11+s1, 12+s2,…,1t+st),1i為Ri的單位元,i=1,2,…,t.x=(x1,x2,…,xt),y=(y1,y2,…,yt)是R的兩個(gè)不同的元.

若x和y在Γ(R,U(R),{-1})中相鄰,則對(duì)于i=1,2,…,t,都有xi-yi∈U(Ri),故xi+siyi∈U(Ri),所以x+sy∈U (R),即x和y在Γ(R,U(R),{s})中相鄰;反過來,若x和y在Γ(R,U(R),{-1})中不相鄰,則存在i∈{1,2,…,t},使得xi-yi∈Mi,所以xi+siyi∈Mi,故x+sy?U(R),即x和y在Γ(R,U(R),{s})中不相鄰.綜上所述,若1+s∈J(R), 則Γ(R,U(R),{s})?Γ(R,U(R),{-1}).

引理7圖G是完美的當(dāng)且僅當(dāng)G和G的補(bǔ)圖G沒有奇洞［2］.

2　主要結(jié)果及證明

文獻(xiàn)［7］證明了,當(dāng)R是偶數(shù)階局部環(huán)時(shí),Γ(R,U(R),{1}和Γ(R,U(R),{-1}是同構(gòu)的,然而,當(dāng)R是偶數(shù)階非局部環(huán),且1+1?J(R)時(shí),Γ(R,U(R),{1})和Γ(R,U(R),{-1})也有可能是同構(gòu)的.

定理1若n=2αpβ,α,β≥1,p是素?cái)?shù)且p＞2,則Γ(Z,nZ,U(Z/nZ),{1})?Γ(Z,nZ,U(Z/nZ),{-1}).

證設(shè)＜2＞為2在Z/nZ中生成的理想,則Γ(Z,nZ,U(Z/nZ),{-1})和Γ(Z,nZ,U(Z/nZ),{1})都是一個(gè)以陪集＜2＞和1+＜2＞為部集的二部圖.定義映射使得,顯然f是一個(gè)雙射.下面分三種情況討論:

（1）若x,y∈Z/nZ恰有一個(gè)是單位,不妨設(shè)x∈U(Z/nZ),則f(y)=y.一方面,若x-y∈U(Z/nZ),則f(x)+f(y)=-x+y=-(x-y)∈(Z/nZ);另一方面,若x+y∈U(Z/nZ),因?yàn)榇嬖?x∈U(R),使得f(-x)=x,所以-x-y=-(x+y)∈U (Z/nZ).因此,x-y∈U(Z/nZ)當(dāng)且僅當(dāng)f(x)+f(y)∈U(Z/nZ).

（2）若x,y∈U(Z/nZ)?1+＜2＞,則x-y?U(Z/nZ)并且x+y?U(Z/nZ).

（3）若x,y?U(Z/nZ),當(dāng)x-y∈U(Z/nZ)時(shí),不妨設(shè)x∈＜2＞,y∈1+＜2＞.因?yàn)閥?U(Z/nZ),所以y必為零因子,因此y=mp∈＜p＞,m是一個(gè)整數(shù).又因?yàn)?x+y)-(x-y)=2y=2mp,因此(x+y)-(x-y)∈＜2＞∩＜p＞.令(x+y)-(xy)=z,注意到Z/nZ只有＜2＞和＜p＞兩個(gè)素理想,故x+y=z+(x-y)∈U(Z/nZ).同理可證,若x+y∈U(Z/nZ),就有xy∈U(Z/nZ).

綜上所述,x與y在Γ(Z,nZ,U(Z/nZ),{-1})中相鄰當(dāng)且僅當(dāng)f(x)與f(y)在Γ(Z,nZ,U(Z/nZ),{1}中相鄰,故Γ(Z, nZ,U(Z/nZ),{1}?Γ(Z,nZ,U(Z/nZ),{-1}.證畢

設(shè)R是一個(gè)含非零單位元的有限交換環(huán).當(dāng)R是一個(gè)局部環(huán)時(shí),Γ(R,U(R),{-1})是一個(gè)完全|R/M|部圖, M是R的極大理想,其團(tuán)數(shù)和頂點(diǎn)著色數(shù)均為|R/M|.取S={s},下面考察當(dāng)1+s∈U(R)時(shí),Γ(R,U(R),S)的團(tuán)數(shù)ω(Γ(R,U(R),S))和頂點(diǎn)著色數(shù)χ(Γ(R,U(R),S)).

證令u=1+s∈U(R),則su=s(1+s),因?yàn)閟·s=1,所以又有su=1+s,即su=u,故s=1,這樣就有Γ(R,U(R), S)=Γ(R,U(R),{1}).由引理2知|R|是奇數(shù),因?yàn)閨U(R)|=|R|-|M|,所以是偶數(shù).

接下來證明χ(Γ(R,U(R),S))≤1+|U(R)|.考慮到{0}∪{x∈|∈A}是一個(gè)具有1+|U(R)|個(gè)頂點(diǎn)的團(tuán),用1+ 22給這個(gè)團(tuán)著色.因?yàn)镸是圖Γ(R,U(R),S)的一個(gè)獨(dú)立集,所以可用0的顏色給M的所有點(diǎn)著色.對(duì)于A的每一個(gè)元,因?yàn)?所以中所包含的任意一點(diǎn)與-r中所包含的任意一點(diǎn)在Γ(R,U(R),S)中不相鄰,因此可用中已有的|M|種顏色為-r中的所有點(diǎn)著色.因此.注意到.證畢.

(1)f1=2;

(2)1+s∈J(R),且t≤2.

證若f1=2,設(shè)M=M1⊕R2⊕…⊕Rt,易知M是R的一個(gè)極大理想,且|R/M|=2.由引理4,Γ(R,U(R),S)是一個(gè)二部圖,所以Γ(R,U(R),S)是一個(gè)完美圖.

若1+s∈J(R),t≤2,由引理5知Γ(R,U(R),S)?Γ(R,U(R),S),{-1},再由引理6 Γ(R,U(R),S)是一個(gè)完美圖.

接下來,考慮當(dāng)f1≥3時(shí)的情形:

(a)若1+s∈J(R)且t≥3,由引理6 Γ(R,U(R),S)不是完美圖.

(b)若1+s?J(R),則t≥2.I={i∈{1,2,…,t}|1i+si∈Mi},易知I和J都是非空集合.取Γ(R,U(R),S)的5個(gè)點(diǎn), a,b,c,d,e,使得:a=(01,02,…,0t);b=(b1,b2,…,bt),若i∈I,則bi=1,否則bi=0;b=(11,12,…,1t);di=(d1,d2,…,dt),若i∈I,則，這里,否則,若以上的0i表示Ri的零元,i∈1,2,…,t.由定理4的證明知,對(duì)任意i∈{1,2,…,t}-I,都有si=li,不難看出a,b,c,d,e是Γ(R,U(R),S)的補(bǔ)圖的一個(gè)長度為5的奇洞,由引理7,Γ(R,U(R),S)不是完美圖.命題得證.

參考文獻(xiàn)：

［1］熊騰飛,簡國明.一類有限交換環(huán)上的廣義單位Cayley圖的若干性質(zhì)［J］.重慶師范大學(xué)學(xué)報(bào)：自然科學(xué)版,2015,32(1):60-63.

［2］Klotz W,Sander T.Some properties of unitary Cayley graphs［J］.Electron J Combin,2007（14）:45.

［3］Akhtar R,Boggess M,Jackson-Henderson T,et al.On the unitary Cayley graph of a finite ring［J］.Electron J Combin,2009 （6）:117.

［4］Kiani D,Aghaei M M H.On the unitary Cayley graph of a ring［J］.Electron J Combin,2012,19(2):10.

［5］Liu X G,Zhou S M.Spectral properties of unitary Cayley graphs of finite commutative rings［J］.Electron J Combin,2012,19(4):13.

［6］Ashrafi N,Maimani H R,Pournaki M R,et al.Unit graphs associated with rings［J］.Comm Algebra,2010（38）:2851-2871.

［7］Khashyarmanesh K,Khorsandi M R.A generalization of the unit and unitary Cayley graphs of a commutative ring［J］.Acta Mathematica Hungarica,2012,137(4):242-253.

［8］West D B.Introduction to Graph theory［M］.2nd ed.New Jersey:Prentice Hall,2000.

［9］馮克勤.交換代數(shù)基礎(chǔ)［M］.北京:高等教育出版社,1986.2.School of Mathematics and Statistics,Shaoguan University,Shaoguan 512005,Guangdong,China）

（責(zé)任編輯：邵曉軍）

中圖分類號(hào)：O157.5

文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：1007-5348（2015）06-0001-04

［收稿日期］2015-03-26

［作者簡介］熊騰飛（1985-），男，廣東韶關(guān)人，韶關(guān)學(xué)院信息科學(xué)與工程學(xué)院教師，碩士；研究方向：環(huán)論、代數(shù)圖論.

Further Study on a Generalization of the Unitary Cayley Graphs of a Finite Commutative Ring

XIONG Teng-fei1,JIAN Guo-ming2
（1.Institute of Information Science and Engineering,Shaoguan University;

Abstract:The paper suggests R be a finite commutative ring with non-zero identity and U(R)be the unit group of R.It also supposes that G is a multiplicative subgroup of U(R),and S is a non-empty subset of G such that S-1= {s-1|s∈S}?S.By the structure of a finite commutative ring,［1］have given some properties of a generalization of the unitary Cayley graphs Γ(R,G,S),where S={s}.The paper makes further research on the properties of Γ(R,U(R),S)where S={s},considering the problem of its isomorphism,achieving the clique number and vertex chromatic number of Γ(R,U(R),S).In addition,it decides Γ(R,U(R),S)is a key to perfect graphs.

Key words:unitary Cayley graphs;clique number;vertex chromatic number;perfect graphs