有限交換環上的廣義單位Cayley圖的進一步研究

熊騰飛，簡國明（.韶關學院 信息科學與工程學院；.韶關學院 數學與統計學院，廣東韶關5005）

有限交換環上的廣義單位Cayley圖的進一步研究

熊騰飛1，簡國明2
（1.韶關學院 信息科學與工程學院；2.韶關學院 數學與統計學院，廣東韶關512005）

摘要：設R是一個含有非零單位元的有限交換環,U(R)是R的單位群,G是U(R)的一個乘法子群,S是G的一個非空子集并且S-1={s-1|s∈S}?S.在研究廣義單位Cayley圖Γ(R,G,S)的若干性質的基礎上，對當S={s}時,Γ(R,U(R), S)的性質作進一步研究，考察Γ(R,U(R),S)的同構問題，得出Γ(R,U(R),S)的團數和頂點著色數,確定Γ(R,U(R),S)是完美圖的條件.

關鍵詞：單位Cayley圖;團數；頂點著色數;完美圖

單位Cayley圖是近年來的一個熱門研究領域,它們內涵豐富,很好地把圖論和代數系統的研究結合起來,提供了研究代數問題的一種新方法.

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

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

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

文獻［1］確定了當S={s}時,廣義單位Cayley圖Γ(R,G,S)的正則性,Γ(R,U(R),S)中任意兩點的公共鄰接點個數以及邊著色數.本文主要對Γ(R,U(R),S)的性質作進一步研究,考察當S={s}時,Γ(R,U(R),{1})與Γ(R,U (R),{-1})的同構問題,計算Γ(R,U(R),S)的團數和頂點著色數，確定Γ(R,U(R),S)是完美圖的條件.

1　定義及引理

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

定義2圖G中長度不小于5并且是奇數的誘導圈稱為奇洞［2］.

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

引理2設R是一個有限環,則1+1∈U(R)當且僅當|R|是奇數.

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

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

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

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

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

證由引理1,設是局部環,其極大理想為Mi,i=1,2,…,t.設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的兩個不同的元.

若x和y在Γ(R,U(R),{-1})中相鄰,則對于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是完美的當且僅當G和G的補圖G沒有奇洞［2］.

2　主要結果及證明

文獻［7］證明了,當R是偶數階局部環時,Γ(R,U(R),{1}和Γ(R,U(R),{-1}是同構的,然而,當R是偶數階非局部環,且1+1?J(R)時,Γ(R,U(R),{1})和Γ(R,U(R),{-1})也有可能是同構的.

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

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

（1）若x,y∈Z/nZ恰有一個是單位,不妨設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),因為存在-x∈U(R),使得f(-x)=x,所以-x-y=-(x+y)∈U (Z/nZ).因此,x-y∈U(Z/nZ)當且僅當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),當x-y∈U(Z/nZ)時,不妨設x∈＜2＞,y∈1+＜2＞.因為y?U(Z/nZ),所以y必為零因子,因此y=mp∈＜p＞,m是一個整數.又因為(x+y)-(x-y)=2y=2mp,因此(x+y)-(x-y)∈＜2＞∩＜p＞.令(x+y)-(xy)=z,注意到Z/nZ只有＜2＞和＜p＞兩個素理想,故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})中相鄰當且僅當f(x)與f(y)在Γ(Z,nZ,U(Z/nZ),{1}中相鄰,故Γ(Z, nZ,U(Z/nZ),{1}?Γ(Z,nZ,U(Z/nZ),{-1}.證畢

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

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

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

(1)f1=2;

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

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

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

接下來,考慮當f1≥3時的情形:

(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個點, 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的證明知,對任意i∈{1,2,…,t}-I,都有si=li,不難看出a,b,c,d,e是Γ(R,U(R),S)的補圖的一個長度為5的奇洞,由引理7,Γ(R,U(R),S)不是完美圖.命題得證.

參考文獻：

［1］熊騰飛,簡國明.一類有限交換環上的廣義單位Cayley圖的若干性質［J］.重慶師范大學學報：自然科學版,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］馮克勤.交換代數基礎［M］.北京:高等教育出版社,1986.2.School of Mathematics and Statistics,Shaoguan University,Shaoguan 512005,Guangdong,China）

（責任編輯：邵曉軍）

中圖分類號：O157.5

文獻標識碼：A

文章編號：1007-5348（2015）06-0001-04

［收稿日期］2015-03-26

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

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