一個對稱圖例的研究

高銳敏 袁澤明

【摘要】如果一個圖的自同構(gòu)群作用在它的弧集上是傳遞的，那么稱這個圖為對稱圖.這里給出了一個2·32階圖例，它是一個點傳遞但邊不傳遞的4度正則圖，可通過找覆蓋圖的方法將其變成對稱圖.

【關(guān)鍵詞】邊不傳遞;全自同構(gòu)群;覆蓋圖;對稱圖

【基金項目】河南省高等學(xué)校青年骨干教師培養(yǎng)計劃（2019GGJS262）

一、引言

本篇文章中若無特別說明，所指的圖均為有限、無向、簡單的連通圖.這里我們用V（X）、E（X）和Aut（X）分別表示圖X的頂點集、邊集和全自同構(gòu)群.對于群理論的常用概念和記號，及一些有關(guān)群理論的性質(zhì)和定理，文獻[1][2]中有詳細(xì)闡述，而一些關(guān)于圖論的概念和性質(zhì)，詳見文獻[3][4][5].

定義1 設(shè)G為有限群，S為不含單位元的子集，我們?nèi)缦露x群G關(guān)于子集S的Cayley（有向）圖X=Cay（G，S）：V（X）=G，E（X）={（g，sg）|g∈G，s∈S}.

命題1 （有向）圖X=（V，E）同構(gòu)于群G的Cayley（有向）圖，當(dāng)且僅當(dāng)Aut（X）包含一個同構(gòu)于群G的正則子群.

定義2 稱圖X是點傳遞、邊傳遞、弧傳遞的，如果Aut（X）傳遞作用在圖X的頂點集上、邊集上、弧集上.

依據(jù)圖的點傳遞性、邊傳遞性及弧傳遞性，可將圖分為不同的類型：點傳遞但邊不傳遞圖、邊傳遞但點不傳遞圖、半傳遞圖、半對稱圖及對稱圖等.

對圖的研究近年來主要集中在Cayley圖上，尤其是討論其正規(guī)性與分類.改變圖的對稱性也是圖論領(lǐng)域研究的一個主題，但是研究結(jié)果表明，圖的對稱性往往是變?nèi)醵皇亲儚?文獻[11]通過找覆蓋圖的方法來增強圖的對稱性，這里給出了一個具體的2·32階圖例，并對其覆蓋圖進行研究.

二、關(guān)于圖X=Z6×Z3的主要結(jié)果

設(shè)V（X）={iji∈Z6，j∈Z3} 與E（X）={{ij，（i+1）j};{ij，ij+1}i∈Z6，j∈Z3}分別為圖X=Z6×Z3的點集合和邊集合，則有如下結(jié)論：

引理1 X=Z6×Z3為點傳遞但邊不傳遞的4度正則圖.

證明：記A=Aut（X），

設(shè)6輪換a：ij→（i+1）j，i∈Z6，j∈Z3，3輪換b：ij→ij+1，i∈Z6，j∈Z3，

顯然有a∈A，b∈A.因此，A在此18個點上傳遞.另外，過邊{11，21}有長為6的圈，而過邊{11，12}沒有長為6的圈，故X邊不傳遞.

命題2 設(shè)G≤SΩ，i∈Ω，則有下述等式成立：GiiG=G，其中iG={igg∈G}.

定理1 設(shè)X=Z6×Z3的全自同構(gòu)群A=Aut（X），則：AD12×D6.

證明：一方面，由6輪換a：ij→（i+1）j，i∈Z6，j∈Z3，顯然有a∈A.

對換b：ij（1-i）j，i∈Z6，j∈Z3，顯然有b∈A.再考慮到ab=a-1且bZ6，所以D12≤A.設(shè)3輪換c：ij→ij+1，i∈Z6，j∈Z3，c∈A.設(shè)對換d：iji1-j，i∈Z6，j∈Z3，又知道d∈A，且cd=c-1，dZ3，所以D6≤A.又ac=a，bc=b，ad=a，bd=b，且有c，d，d，c，故D12×D6≤A.

另一方面，由點傳遞性，知A=1A1A11=18A11，又A11=2A111A11，21，由于21在A11的作用下能且僅能變到61，因此A11=2A111A11，21=2A11，21，令B=A11，21，顯然B也固定61，從而也固定31，51，41，于是B=A11，21，31，41，51，61，又B=1B2B12，因為12在B的作用下能且僅能變到13，所以B=2B12，不難觀察到B12也固定了13.B12已經(jīng)固定了11的4個鄰點，從而也固定其余各點，故B12=1.因此A=18×4=72.

綜上可知，AD12×D6.

[STHZ]三、覆蓋圖[STBZ]

定理2 圖Y為帶有自環(huán)的C3的Z6覆蓋，其中圈C3的任兩點（不妨設(shè)第2個點與第3個點）之間加電壓值3，其余均為平凡電壓，則有：Y為2·32階的4度對稱圖.

證明：圖Y的頂點集：V（Y）={iji∈Z6，j∈Z3};

圖Y的邊集：E（Y）={{ij，（i+1）j}，{i1，i2}，{i3，i1}，{i2，（i+3）3}i∈Z6，j∈Z3}.

設(shè)a：1111;2222;3333;4141;5252;6363;2112;3143;5142;6113;5332;2362.

b：ij→（i+1）j，i∈Z6，j∈Z3.

c：ij→ij+1，i∈Z6，j∈Z3-{2}，i2→（i+3）3，i∈Z6.

d：ij（2-i）j，i∈Z6，j∈Z3.

記A=Aut（Y），下面驗證a∈A.

先驗證{ij，（i+1）j}a∈E（Y），i∈Z6，j∈Z3：

{11，21}a={11，12};{21，31}a={12，43};{31，41}a={43，41};{41，51}a={41，42};

{51，61}a={42，13};{61，11}a={13，11};{12，22}a={21，22};{22，32}a={22，53};

{32，42}a={53，51};{42，52}a={51，52};{52，62}a={52，23};{62，12}a={23，21};