李映輝 ， 王守峰

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

0 引言

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

文獻(xiàn)[7]首次給出了廣義Brandt半群的代數(shù)結(jié)構(gòu)， 是完全0-單的純正半群. 本研究的目的是利用這一代數(shù)結(jié)構(gòu)在文獻(xiàn)[8]的基礎(chǔ)上， 拓廣Cayley圖連接集及導(dǎo)出子集， 研究廣義Brandt半群上分別以SIλ-、S-Jλ和SIλJλ為連接集的Cayley圖. 通過(guò)對(duì)連接集為L(zhǎng)-類(lèi)、R-類(lèi)和H-類(lèi)等三類(lèi)Green等價(jià)類(lèi)在廣義Brandt半群上的Cayley圖間的同構(gòu)條件的討論， 刻畫(huà)了這三類(lèi)Cayley圖的結(jié)構(gòu).

1 預(yù)備知識(shí)

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

設(shè)S是半群，A是S的子集， 定義Cayley圖Cay(S，A)如下： 其頂點(diǎn)集V(Cay(S，A))=S， 對(duì)任意頂點(diǎn)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)是空?qǐng)D.因此在本研究中設(shè)A是S的非空子集.據(jù)文獻(xiàn)[10]， 半群S的以下Green等價(jià)關(guān)系成立.對(duì)任意的a，b∈S， 有：

aLb?S1a=S1b；aRb?aS1=bS1

記H=L∩R.易見(jiàn)， 對(duì)任意的a，b∈S，aLb當(dāng)且僅當(dāng)a=b或者存在x，y∈S， 使得a=xb和b=ya.對(duì)關(guān)系R和H也有類(lèi)似結(jié)果.

完全0-單的純正半群稱為廣義Brandt半群. Yamada在文獻(xiàn)[7]中給出的這類(lèi)半群的如下結(jié)構(gòu)定理.

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

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

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

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

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

2 主要定理與結(jié)果

本節(jié)討論廣義Brandt半群S關(guān)于L-類(lèi)、R-類(lèi)和H-類(lèi)的Cayley圖.對(duì)于給定的λ，μ∈Λ有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-類(lèi)和R-類(lèi).

2.1 廣義Brandt半群關(guān)于L-類(lèi)S-Jμ的Cayley圖

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

證明 充分性顯然.

下證必要性： 設(shè)(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設(shè)(u，g，v)， (s，h，t)∈S， 在廣義Brandt半群S關(guān)于L- 類(lèi)S-Jμ的Cayley圖Cay(S，S-Jμ)中， (u，g，v)～(s，h，t)當(dāng)且僅當(dāng)v=t，u∈Iμ， 而(u，g，v)～0當(dāng)且僅當(dāng)u?Iμ.

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

① 對(duì)任意v∈Jμ， 由Iμ×G×{v}的導(dǎo)出子圖是完全圖K|Iμ||G|；

② 若λ≠μ(λ=μ)， 則由SIλ-導(dǎo)出的子圖是空?qǐng)D(K|Iλ||G|)；

證明 ① 任取兩點(diǎn)(s，g，v)， (t，h，v)∈Iμ×G×{v}， 因?yàn)関∈Jμ，s，t∈Iμ， 根據(jù)命題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}的導(dǎo)出子圖是完全圖K|Iμ||G|.

② 如果λ≠μ， 對(duì)于任意的i1，i2∈Iλ， (i1，g，u)， (i2，h，u)∈SIλ-， 在連接集S-Jμ中找不到任何元使(i1，g，u)～(i2，h，u)成立， 所以Cayley圖Cay(S，S-Jμ)由SIλ-的導(dǎo)出子圖是空?qǐng)D； 如果λ=μ， 對(duì)于任意的(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λ-的導(dǎo)出子圖是完全圖K|Iλ||G|.

③ 當(dāng)u∈Iμ時(shí)， 對(duì)任意(i，x，j)∈S-Jμ， 有pju=1， 這表明頂點(diǎn)a=(u，g，v)出度為:

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

④ 考慮頂點(diǎn)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設(shè)λ，μ∈Λ， 則廣義Brand半群S的兩個(gè)L-類(lèi)S-Jλ和S-Jμ的Cayley圖Cay(S，S-Jλ)與Cay(S，S-Jμ)同構(gòu)當(dāng)且僅當(dāng)|Iλ|=|Iμ|.

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

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

情形1a=0，b=0.此時(shí)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)， 再次根據(jù)推論1， 在Cayley圖Cay(S，S-Jμ)中， 連接集中存在(*，yx-1，l)∈S-Jμ， 使得:(*，y，v)=(*，yx-1，l)(uψλ， μ，x，v).其中，pl， uψλ， μ=1， 即aφ～bφ.完全可以類(lèi)似證明φ-1也是一個(gè)圖同態(tài).

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

2.2 廣義Brandt半群S關(guān)于R-類(lèi)SIλ-的Cayley圖

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

Ⅰ) 對(duì)于任意頂點(diǎn)(u，g，v)， (s，h，t)∈S， 則(u，g，v)～(s，h，t)當(dāng)且僅當(dāng)v=t和s∈Iλ；

Ⅱ) 頂點(diǎn)0的出度是1.當(dāng)|Λ|=1(|Λ|≥2)時(shí)， 頂點(diǎn)(u，g，v)的出度為:|Iλ||G|(|Iλ||G|+1)；

Ⅲ) 當(dāng)|Λ|=1(|Λ|≥2)時(shí)， 頂點(diǎn)0的入度是1(|S|)；

Ⅳ) 若u?Iλ(u∈Iλ)， 則頂點(diǎn)(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λ的導(dǎo)出子圖Cay(S-Jλ，Si-)是同構(gòu)于一個(gè)完全二部圖Krn， n與一個(gè)星圖K1， (m-r)n的并圖Γ1.其中，m=|I|，r=|Iλ|，n=|G|.

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

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

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

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

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

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

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

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

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

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

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

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

2.3 廣義Brandt半群關(guān)于H-類(lèi)的Cayley圖

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

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

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

b) 頂點(diǎn)0的出度為1， 當(dāng)u∈Iλ時(shí)， 頂點(diǎn)a的出度為|Iλ||G|； 當(dāng)u?Iλ時(shí)， 頂點(diǎn)a的出度為1;

c) 頂點(diǎn)0的入度是:(|I|-|Iλ|)|G||J|+1.當(dāng)u?Iλ(u∈Iλ)時(shí)， 頂點(diǎn)a的入度為0(|Iλ||G|).

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

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

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

同時(shí)，Pjs=1成立.

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

證明 在Cayley圖Cay(SIλ-，SIλJλ)中， 因?yàn)閷?duì)任意(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)， 對(duì)應(yīng)在一個(gè)左群Iλ×G的Cayley圖Cay(Iλ×G，Iλ×G)中， 當(dāng)且僅當(dāng)對(duì)任意(u，x)， (v，y)∈Iλ×G， 在連接集中總存在(v，yx-1)， (u，xy-1)∈Iλ×G， 使得:(u，x)～(v，y)和(v，y)～(u，x).保持點(diǎn)的鄰接關(guān)系， 所以映射:φ:(u，x，j)(u，x)是一個(gè)從Cayley圖Cay(SIλ-，SIλJλ)到左群Iλ×G的Cayley圖Cay(Iλ×G，Iλ×G)的圖同構(gòu)映射， 故Cay(SIλ-，SIλJλ)與Cay(Iλ×G，Iλ×G)同構(gòu).

而在左群Cayley圖Cay(Iλ×G，Iλ×G)中， 對(duì)任一(u，x)∈Iλ×G， 因?yàn)閨Iλ×G|=|Iλ||G|=rn總存在rn個(gè)點(diǎn)(v，y)∈Iλ×G， 使得: (u，x)～(v，y)， 所以Cayley圖Cay(Iλ×G，Iλ×G)同構(gòu)于完全圖Krn.

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

證明 因?yàn)橹笜?biāo)集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的兩個(gè)Cayley圖Cay(S，SIλJλ)與Cay(S，SIμJμ)同構(gòu)當(dāng)且僅當(dāng)|Iλ|=|Iμ|.

證明 設(shè)|I|=m， |Iλ|=r， |Iμ|=s以及|G|=n， 根據(jù)定理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μ)， 當(dāng)且僅當(dāng)r=s， 即|Iλ|=|Iμ|.

3 結(jié)語(yǔ)

本研究在文獻(xiàn)[8]廣義Brandt半群上分別以Si-,S-j和Sij為連接集的Cayley圖的研究基礎(chǔ)上， 拓廣Cayley圖連接集及導(dǎo)出子集， 討論了廣義Brandt半群上分別以SIλ-，S-Jλ和SIλJλ為連接集的Cayley圖.通過(guò)對(duì)連接集為L(zhǎng)-類(lèi)，R-類(lèi)和H-類(lèi)等三類(lèi)Green等價(jià)類(lèi)在廣義Brandt半群上的Cayley圖間的同構(gòu)條件的討論， 刻畫(huà)了這三類(lèi)Cayley圖的結(jié)構(gòu)， 揭示了廣義Brandt半群是一個(gè)完全0-單的純正半群的本質(zhì)特征， 突出了研究方法的系統(tǒng)化.