廣義Brandt半群的另一類Cayley圖

李映輝 ， 王守峰

(1. 昆明學院教師教育學院, 云南 昆明 650204； 2. 云南師范大學數學學院, 云南 昆明 650500)

0 引言

研究半群Cayley圖， 通常是利用圖的組合性質刻畫半群的結構， 或利用半群的代數結構刻畫圖的組合性質， 從而建立起圖論與半群理論之間的聯系. 半群Cayley圖的研究可追溯到文獻[1]， 2003年文獻[2]中首次研究了半群上Cayley 圖的點傳遞性. 受此啟發和鼓舞， 眾多學者展開了半群Cayley圖的研究. 文獻[3]研究了特殊半群(逆半群、 完全0-單半群)上的Cayley 圖的結構和性質. Brandt半群是一類重要的半群， 是完全0-單的逆半群. Brandt半群上的Cayley圖得到了許多學者的重視. 文獻[4-6]研究了Brandt半群上以Geeen等價類為連接集的Cayley 圖及其同構條件.

文獻[7]首次給出了廣義Brandt半群的代數結構， 是完全0-單的純正半群. 本研究的目的是利用這一代數結構在文獻[8]的基礎上， 拓廣Cayley圖連接集及導出子集， 研究廣義Brandt半群上分別以SIλ-、S-Jλ和SIλJλ為連接集的Cayley圖. 通過對連接集為L-類、R-類和H-類等三類Green等價類在廣義Brandt半群上的Cayley圖間的同構條件的討論， 刻畫了這三類Cayley圖的結構.

1 預備知識

對有向圖Γ=(V，E)，V′?V，Γ=(V，E)的一個以V′作為頂點集， 以兩個端點都屬于V′的在原圖Γ=(V，E)中的弧作為弧集的子圖被稱為V′導出子圖， 記作Γ(V′).對于任意的正整數m，n， 完全圖Km是指有m個頂點， 其中每個頂點都與其他頂點連接的圖；nKm是n個完全圖Km復制的不交并.一個r-部圖是指一個圖的頂點被分成r個子集V1，V2， …，Vr的不交并， 且在同一個子集中的任兩點不連接； 完全r-部圖是一個所有來自不同子集的任意兩點均連接的r-部圖.特別地， 完全二部圖的頂點集是V=V1∪V2， 若|V1|=m，|V2|=n， 則記為Km， n， 而K1， n稱為星圖.對兩個有向圖Γ1=(V1，E1)和Γ2=(V2，E2)， 圖同態φ:Γ1→Γ2是一個滿足： (u，v)∈E1?(φ(u)，φ(v))∈E2的映射φ:V1→V2； 若映射φ:Γ1→Γ2是個雙射， 且φ和φ-1都是圖同態， 則稱φ為圖Γ1到Γ2同構映射， 此時稱圖Γ1與Γ2同構， 記作Γ1?Γ2； 圖同態φ:Γ→Γ稱為自同態， 圖同構φ:Γ→Γ稱為自同構.文中未說明的術語和符號， 可參考文獻[9-10].

設S是半群，A是S的子集， 定義Cayley圖Cay(S，A)如下： 其頂點集V(Cay(S，A))=S， 對任意頂點u，v∈S， 稱(u，v)(或者u～v)是Cay(S，A)的一條邊， 如果存在a∈A， 使得v=au.即邊集為：

E(Cay(S，A))={(s，as):s∈S，a∈A}

集合A稱為Cayley圖Cay(S，A)的連接集， 若A是空子集， 則Cayley圖Cay(S，A)是空圖.因此在本研究中設A是S的非空子集.據文獻[10]， 半群S的以下Green等價關系成立.對任意的a，b∈S， 有：

aLb?S1a=S1b；aRb?aS1=bS1

記H=L∩R.易見， 對任意的a，b∈S，aLb當且僅當a=b或者存在x，y∈S， 使得a=xb和b=ya.對關系R和H也有類似結果.

完全0-單的純正半群稱為廣義Brandt半群. Yamada在文獻[7]中給出的這類半群的如下結構定理.

定理1[7]設G0是一個0-群(在群G上添加0元得到的半群).I和J是非空集，P=(pji)是一個J×I-矩陣， {Iλ:λ∈Λ}和{Jμ:μ∈Λ}分別是集合I和J的不交子集族(其中Λ是一個指標集)， 且滿足下列條件：

2) 對任意的λ，μ∈Λ和j∈Jμ，i∈Iλ， 有：

則S=(I×G×J)∪{0}關于下列運算：

構成廣義Brandt半群， 記之為S=M0(I，J;G;P;Λ).反之， 任何廣義Brandt半群均可如此構造.

以下恒設S=M0(I，J;G;P;Λ)是廣義Brandt半群.

2 主要定理與結果

本節討論廣義Brandt半群S關于L-類、R-類和H-類的Cayley圖.對于給定的λ，μ∈Λ有Iλ，Jμ記:

S-Jμ={(i，g，j):i∈I，g∈G，j∈Jμ}，SIλ-={(i，g，j):i∈Iλ，g∈G，j∈J}

則S-Jμ，SIλ-分別是S的所有L-類和R-類.

2.1 廣義Brandt半群關于L-類S-Jμ的Cayley圖

命題1設A?S， (u，g，v)， (s，h，t)∈S， 且u∈Iλ， 則在廣義Brandt半群S的Cayley圖Cay(S，A)中， (u，g，v)～(s，h，t)當且僅當v=t且存在j∈Jλ， 有: (s，hg-1，j)∈A.

證明 充分性顯然.

下證必要性： 設(u，g，v)～(s，h，t)，u∈Iλ， 則存在(i，x，j)∈A， 其中j∈Jλ， 使(s，h，t)=(i，x，j)(u，g，v)， 這表明pju=1，s=i，v=t且x=hg-1.于是有(s，hg-1，j)∈A.

推論1設(u，g，v)， (s，h，t)∈S， 在廣義Brandt半群S關于L- 類S-Jμ的Cayley圖Cay(S，S-Jμ)中， (u，g，v)～(s，h，t)當且僅當v=t，u∈Iμ， 而(u，g，v)～0當且僅當u?Iμ.

命題2在廣義Brandt半群S的Cayley圖Cay(S，S-Jμ)中， 有以下結論：

① 對任意v∈Jμ， 由Iμ×G×{v}的導出子圖是完全圖K|Iμ||G|；

② 若λ≠μ(λ=μ)， 則由SIλ-導出的子圖是空圖(K|Iλ||G|)；

證明 ① 任取兩點(s，g，v)， (t，h，v)∈Iμ×G×{v}， 因為v∈Jμ，s，t∈Iμ， 根據命題1， 總存在(t，hg-1，v)∈S-Jμ和(s，gh-1，v)∈S-Jμ， 使得pvs=1和pvt=1， 那么(t，h，v)=(t，hg-1，v)(s，g，v)和(s，g，v)=(s，gh-1，v)(t，h，v)成立.而|Iμ×G×{v}|=|Iμ||G|， 所以Cayley圖Cay(S，S-Jμ)由Iμ×G×{v}的導出子圖是完全圖K|Iμ||G|.

② 如果λ≠μ， 對于任意的i1，i2∈Iλ， (i1，g，u)， (i2，h，u)∈SIλ-， 在連接集S-Jμ中找不到任何元使(i1，g，u)～(i2，h，u)成立， 所以Cayley圖Cay(S，S-Jμ)由SIλ-的導出子圖是空圖； 如果λ=μ， 對于任意的(i1，g，u)， (i2，h，u)∈SIμ-， 由式(1)知， 總存在pj1i1=1和pj2i2=1， 且(i2，hg-1，j1)， (i1，gh-1，j2)∈S-Jμ， 使得: (i1，g，u)～(i2，h，u)和(i2，h，u)～(i1，g，u)成立， 所以Cay(S，S-Jλ)由SIλ-的導出子圖是完全圖K|Iλ||G|.

③ 當u∈Iμ時， 對任意(i，x，j)∈S-Jμ， 有pju=1， 這表明頂點a=(u，g，v)出度為:

=|{(i，y，v):i∈I，y∈G}|=|I||G|

④ 考慮頂點a=(u，g，v)的入度， 首先pjs=1，有：

考慮0的入度， 由③的證明知只需討論u?Iμ的情形:

=|{(u，g，v):u?Iμ，g∈G，v∈J}∪{0}|

=|{(u，g，v):u?Iμ，g∈G，v∈J}|+1=(|I|-|Iμ|)|G||J|+1

定理2設λ，μ∈Λ， 則廣義Brand半群S的兩個L-類S-Jλ和S-Jμ的Cayley圖Cay(S，S-Jλ)與Cay(S，S-Jμ)同構當且僅當|Iλ|=|Iμ|.

充分性： 若λ=μ， 顯然成立.若λ≠μ， 由于|Iλ|=|Iμ|， 可設ψλ， μ:Iλ→Iμ是一個雙射， 定義映射φ:S→S， 規定0φ=0， 對于任意的a=(u，x，v)， 有:

顯然φ是一個雙射， 下證φ是一個圖同態.設a=(u，g，v)，b=(s，h，t)∈S且在Cayley圖Cay(S，S-Jλ)中有a～b.下面分情況討論.

情形1a=0，b=0.此時aφ=bφ=0， 在Cayley圖Cay(S，S-Jμ)中自然有0～0， 即aφ～bφ.

情形3a≠0且b≠0.由于在Cayley圖Cay(S，S-Jλ)中a～b， 必有u∈Iλ， 那么aφ=(uψλ， μ，x，v)，uψλ， μ∈Iμ， 而bφ=(s，y，v)φ=(*，y，v)， 再次根據推論1， 在Cayley圖Cay(S，S-Jμ)中， 連接集中存在(*，yx-1，l)∈S-Jμ， 使得:(*，y，v)=(*，yx-1，l)(uψλ， μ，x，v).其中，pl， uψλ， μ=1， 即aφ～bφ.完全可以類似證明φ-1也是一個圖同態.

綜上所述， 有Cay(S，S-Jλ)?Cay(S，S-Jμ).證畢.

2.2 廣義Brandt半群S關于R-類SIλ-的Cayley圖

命題3在廣義Brandt半群S關于R-類SIλ-的Cayley圖Cay(S，SIλ-)中， 下列結論成立：

Ⅰ) 對于任意頂點(u，g，v)， (s，h，t)∈S， 則(u，g，v)～(s，h，t)當且僅當v=t和s∈Iλ；

Ⅱ) 頂點0的出度是1.當|Λ|=1(|Λ|≥2)時， 頂點(u，g，v)的出度為:|Iλ||G|(|Iλ||G|+1)；

Ⅲ) 當|Λ|=1(|Λ|≥2)時， 頂點0的入度是1(|S|)；

Ⅳ) 若u?Iλ(u∈Iλ)， 則頂點(u，g，v)的入度為0(|I||G|).

證明 Ⅰ) 由命題1立得.

=|{(i，x，j)(u，g，v):i∈Iλ，j∈Jμ，x∈G}∪{(i，x，j)(u，g，v):i∈Iλ，j∈Jγ，x∈G}|

=|{(i，y，v):i∈Iλ，y∈G}∪{0}|=|Iλ||G|+1

=|{(s，h-1g，v):s∈I，h∈G}|=|I||G|

定理3廣義Brandt半群S的Cayley圖Cay(S，Si-)由S-Jλ的導出子圖Cay(S-Jλ，Si-)是同構于一個完全二部圖Krn， n與一個星圖K1， (m-r)n的并圖Γ1.其中，m=|I|，r=|Iλ|，n=|G|.

證明 在廣義Brandt半群S的Cayley圖Cay(S，Si-)(i∈Iλ)由S-Jλ的導出子圖Cay(S-Jλ，Si-)中， 依據命題3中Ⅰ)， 分兩方面討論：

一方面，u∈Iλ， 對任意(u，x，j1)∈S-Jλ， 存在(i，g，j2)∈Si-， 使得:(u，x，j1)～(i，gx，j1).根據命題3中Ⅱ)有:|{(u，x，j1):u∈Iλ，x∈G，j1∈Jλ}|=|Iλ×G×{j1}|=|Iλ||G|=rn， |{i}||G||{j1}|=|G|=n， 根據廣義Brandt半群S的Cayley圖定義， Cayley圖Cay(S-Jλ，Si-)同構于一個完全二部圖Krn， n.

另一方面，u?Iλ， 對任意(u，x，j1)∈S-Jλ， 在廣義Brandt半群S的Cayley圖Cay(S，Si-)(i∈Iλ)由S-Jλ的導出子圖Cay(S-Jλ，Si-)中， 均有: (u，x，j1)～0， 此時Cayley圖Cay(S-Jλ，Si-)同構于一個星圖K1， (m-r)n.

綜上所述， Cay(S-Jλ，Si-)同構于一個完全二部圖Krn， n與一個星圖K1， (m-r)n的并圖， 即:

Cay(S-Jλ，Si-)?Krn， n+K1， (m-r)n=Γ1

定理4廣義Brandt半群S的Cayley圖Cay(S，SIμ-)由S-Jλ的導出子圖Cay(S-Jλ，SIμ-)同構于t個完全二部圖tKrn， n與一個星圖K1， (m-r)n的并圖， 即Cay(S-Jλ，SIμ-)?tKrn， n+K1， (m-r)n=Γ2.其中m=|I|，r=|Iλ|，t=|Iμ|和n=|G|.

證明 在定理3的證明過程中， 注意到在Cayley圖Cay(S，SIμ-)由S-Jλ的導出子圖Cay(S-Jλ，SIμ-)中， |Iμ|=t， 當u∈Iλ時， 每個頂點的出度是在Cayley圖Cay(S-Jλ，Si-)中的t倍.所以導出子圖Cay(S-Jλ，SIμ-)同構于t個完全二部圖tKrn， n與一個星圖K1， (m-r)n的并圖， 即:

Cay(S-Jλ，SIμ-)?tKrn， n+K1， (m-r)n=Γ2

作為以上定理的推廣， 有如下系列結論.

定理5ⅰ) 對于j∈Jλ，k∈Jγ， 那么Cayley圖Cay(S，Si-)由S-j和S-l的兩個導出子圖Cay(S-j，Si-)與Cay(S-k，Si-)同構的充分必要條件是|Iλ|=|Iγ|;

ⅱ) 對于任意λ，γ∈Λ， Cayley圖Cay(S，Si-)分別由S-Jλ和S-Jγ導出的兩個子圖Cay(S-Jλ，Si-)與Cay(S-Jγ，Si-)同構的充分必要條件是|Iλ|=|Iγ|;

ⅲ)對于任意λ，γ，μ∈Λ， 那么Cayley圖Cay(S，SIμ-)分別由S-Jλ和S-Jγ導出的兩個子圖Cay(S-Jλ，SIμ-)與Cay(S-Jγ，SIμ-)同構的充分必要條件是|Iλ|=|Iγ|.

2.3 廣義Brandt半群關于H-類的Cayley圖

對于集合SIλJμ={(i，g，j):i∈Iλ，g∈G，j∈Jμ}， 若λ≠μ， 則不構成H-類， 所以本節討論廣義Brandt半群關于H-類SIλJλ的Cayley圖Cay(S，SIλJλ).

命題4在廣義Brandt半群S關于H-類SIλJλ的Cayley圖Cay(S，SIλJλ)中， 設a=(u，g，v)，b=(s，h，t)∈S， 下列結論成立：

a) (u，g，v)～(s，h，t)當且僅當v=t，s，u∈Iλ， 而(u，g，v)～0當且僅當u?Iλ;

b) 頂點0的出度為1， 當u∈Iλ時， 頂點a的出度為|Iλ||G|； 當u?Iλ時， 頂點a的出度為1;

c) 頂點0的入度是:(|I|-|Iλ|)|G||J|+1.當u?Iλ(u∈Iλ)時， 頂點a的入度為0(|Iλ||G|).

證明 a) 根據命題1直接得證.

=|{(i，y，v):i∈Iλ，y∈G}|=|Iλ||G|

=|{(s，x-1g，v):s∈Iλ，x∈G}|=|Iλ||G|

同時，Pjs=1成立.

命題5廣義Brandt半群S關于H-類SIλJλ的Cayley圖Cay(SIλ-，SIλJλ)與一個左群Iλ×G的Cayley圖Cay(Iλ×G，Iλ×G)同構.而左群的Cayley圖Cay(Iλ×G，Iλ×G)同構于一個完全圖Krn.其中， |Iλ|=r和|G|=n.

證明 在Cayley圖Cay(SIλ-，SIλJλ)中， 因為對任意(u，x，j)， (v，y，j)∈SIλ-， 總存在(v，yx-1，j1)∈SIλJλ和(u，xy-1，j2)∈SIλJλ， 由于u，v∈Iλ，j1，j2∈Jλ，pj1u=1，pj2v=1使得:(v，y，j)=(v，yx-1，j1)(u，x，j)和(u，x，j)=(u，xy-1，j2)(v，y，j)成立.即(u，x，j)～(v，y，j)和(v，y，j)～(u，x，j)， 對應在一個左群Iλ×G的Cayley圖Cay(Iλ×G，Iλ×G)中， 當且僅當對任意(u，x)， (v，y)∈Iλ×G， 在連接集中總存在(v，yx-1)， (u，xy-1)∈Iλ×G， 使得:(u，x)～(v，y)和(v，y)～(u，x).保持點的鄰接關系， 所以映射:φ:(u，x，j)(u，x)是一個從Cayley圖Cay(SIλ-，SIλJλ)到左群Iλ×G的Cayley圖Cay(Iλ×G，Iλ×G)的圖同構映射， 故Cay(SIλ-，SIλJλ)與Cay(Iλ×G，Iλ×G)同構.

而在左群Cayley圖Cay(Iλ×G，Iλ×G)中， 對任一(u，x)∈Iλ×G， 因為|Iλ×G|=|Iλ||G|=rn總存在rn個點(v，y)∈Iλ×G， 使得: (u，x)～(v，y)， 所以Cayley圖Cay(Iλ×G，Iλ×G)同構于完全圖Krn.

定理6廣義Brandt半群S關于H-類SIλJλ的Cayley圖Cay(S，SIλJλ)與完全圖Krn和星圖Γ1， (m-r)n的并圖同構.其中|Iλ|=r和|G|=n.

證明 因為指標集I=Iλ∪IIλ， 由命題5知Cay(SIλ-，SIλJλ)?Krn， 所以下式成立：

Cay(S，SIλJλ)?Cay(SIλ-，SIλJλ)+Γ1， (m-r)n?Krn+Γ1， (m-r)n

定理7廣義Brandt半群S的兩個Cayley圖Cay(S，SIλJλ)與Cay(S，SIμJμ)同構當且僅當|Iλ|=|Iμ|.

證明 設|I|=m， |Iλ|=r， |Iμ|=s以及|G|=n， 根據定理6有: Cayley圖Cay(S，SIλJλ)?Krn+Γ1， (m-r)n和Cayley圖Cay(S，SIμJμ)?Ksn+Γ1， (m-s)n.所以Cay(S，SIλJλ)?Cay(S，SIμJμ)， 當且僅當r=s， 即|Iλ|=|Iμ|.

3 結語

本研究在文獻[8]廣義Brandt半群上分別以Si-,S-j和Sij為連接集的Cayley圖的研究基礎上， 拓廣Cayley圖連接集及導出子集， 討論了廣義Brandt半群上分別以SIλ-，S-Jλ和SIλJλ為連接集的Cayley圖.通過對連接集為L-類，R-類和H-類等三類Green等價類在廣義Brandt半群上的Cayley圖間的同構條件的討論， 刻畫了這三類Cayley圖的結構， 揭示了廣義Brandt半群是一個完全0-單的純正半群的本質特征， 突出了研究方法的系統化.