一个对称图例的研究

    高锐敏 袁泽明

    

    

    【摘要】如果一个图的自同构群作用在它的弧集上是传递的，那么称这个图为对称图.这里给出了一个2·32阶图例，它是一个点传递但边不传递的4度正则图，可通过找覆盖图的方法将其变成对称图.

    【关键词】边不传递;全自同构群;覆盖图;对称图

    【基金项目】河南省高等学校青年骨干教师培养计划（2019GGJS262）

    一、引言

    本篇文章中若无特别说明，所指的图均为有限、无向、简单的连通图.这里我们用V（X）、E（X）和Aut（X）分别表示图X的顶点集、边集和全自同构群.对于群理论的常用概念和记号，及一些有关群理论的性质和定理，文献[1][2]中有详细阐述，而一些关于图论的概念和性质，详见文献[3][4][5].

    定义1 设G为有限群，S为不含单位元的子集，我们如下定義群G关于子集S的Cayley（有向）图X=Cay（G，S）：V（X）=G，E（X）={（g，sg）|g∈G，s∈S}.

    命题1 （有向）图X=（V，E）同构于群G的Cayley（有向）图，当且仅当Aut（X）包含一个同构于群G的正则子群.

    定义2 称图X是点传递、边传递、弧传递的，如果Aut（X）传递作用在图X的顶点集上、边集上、弧集上.

    依据图的点传递性、边传递性及弧传递性，可将图分为不同的类型：点传递但边不传递图、边传递但点不传递图、半传递图、半对称图及对称图等.

    对图的研究近年来主要集中在Cayley图上，尤其是讨论其正规性与分类.改变图的对称性也是图论领域研究的一个主题，但是研究结果表明，图的对称性往往是变弱而不是变强.文献[11]通过找覆盖图的方法来增强图的对称性，这里给出了一个具体的2·32阶图例，并对其覆盖图进行研究.

    二、关于图X=Z6×Z3的主要结果

    设V（X）={iji∈Z6，j∈Z3} 与E（X）={{ij，（i+1）j};{ij，ij+1}i∈Z6，j∈Z3}分别为图X=Z6×Z3的点集合和边集合，则有如下结论：

    引理1 X=Z6×Z3为点传递但边不传递的4度正则图.

    证明：记A=Aut（X），

    设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 设G≤SΩ，i∈Ω，则有下述等式成立：GiiG=G，其中iG={igg∈G}.

    定理1 设X=Z6×Z3的全自同构群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.设3轮换c：ij→ij+1，i∈Z6，j∈Z3，c∈A.设对换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已经固定了11的4个邻点，从而也固定其余各点，故B12=1.因此A=18×4=72.

    综上可知，AD12×D6.

    [STHZ]三、覆盖图[STBZ]

    定理2 图Y为带有自环的C3的Z6覆盖，其中圈C3的任两点（不妨设第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}.

    设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};

    {13，23}a={61，62};{23，33}a={62，33};{33，43}a={33，31};{43，53}a={31，32};

    {53，63}a={32，63};{63，13}a={63，61}.显然有{ij，（i+1）j}a∈E（Y），i∈Z6，j∈Z3.

    再验证{i1，i2}a∈E（Y），{i3，i1}a∈E（Y），i∈Z6：

    {11，12}a={11，21}∈E（Y）;{21，22}a={12，22}∈E（Y）;{31，32}a={43，53}∈E（Y）;

    {41，42}a={41，51}∈E（Y）;{51，52}a={42，52}∈E（Y）;{61，62}a={13，23}∈E（Y）.

    {13，11}a={61，11}∈E（Y）;{23，21}a={62，12}∈E（Y）;{33，31}a={33，43}∈E（Y）;

    {43，41}a={31，41}∈E（Y）;

    {53，51}a={32，42}∈E（Y）;{63，61}a={63，13}∈E（Y）.

    最后验证{i2，（i+3）3}a∈E（Y），i∈Z6：

    {12，43}a={21，31}∈E（Y）;{22，53}a={22，32}∈E（Y）;

    {32，63}a={53，63}∈E（Y）;

    {42，13}a={51，61}∈E（Y）;{52，23}a={52，62}∈E（Y）;

    {62，33}a={23，33}∈E（Y）.

    综上所述，a∈A.

    因为i∈Z6，j∈Z3，都有

    {ij，（i+1）j}b={（i+1）j，（i+2）j}∈E（Y）;{i1，i2}b={（i+1）1，（i+1）2}∈E（Y）;

    {i3，i1}b={（i+1）3，（i+1）1}∈E（Y）;{i2，（i+3）3}b={（i+1）2，（i+4）3}∈E（Y）

    成立，所以b∈A.

    下面验证c∈A：

    {ij，（i+1）j}c={ij+1，（i+1）j+1}∈E（Y），i∈Z6，j∈Z3-{2}，{（i+3）3，（i+4）3}∈E（Y），i∈Z6，j=2;

    {i1，i2}c={i2，（i+3）3}∈E（Y），i∈Z6;

    {i3，i1}c={i1，i2}∈E（Y），i∈Z6;

    {i2，（i+3）3}c={（i+3）3，（i+3）1}∈E（Y），i∈Z6.

    故c∈A.

    又因為i∈Z6，j∈Z3，都有

    {ij，（i+1）j}d={（2-i）j，（1-i）j}∈E（Y）;{i1，i2}d={（2-i）1，（2-i）2}∈E（Y）;

    {i3，i1}d={（2-i）3，（2-i）1}∈E（Y）;{i2，（i+3）3}d={（2-i）2，（5-i）3}∈E（Y）

    成立，因此d∈A.

    容易观察到≤A在V（Y）上传递，即图Y点传递.

    点11的4个邻点分别为：21，61，12，13.设H=A11，由2〈a〉1=12，1〈a〉2=21，6〈a〉1=13，1〈a〉3=61，2〈d〉1=61，且a∈H，d∈H，知H在点11的4个邻点上传递，因此Y为对称图.

    又因为1b1=21，1b-11=61，1c1=12，1c1-1=13，所以图Y是关于集合b，b-1，c，c-1的Cayley图.不难证明Z6，bc=b，c3=b3，又c2为3阶元，c2，因此，Z6×Z3.故Y是交换群Z6×Z3的Cayley图.

    【参考文献】

    [1]徐明曜.有限群导引（上册）[M].北京：科学出版社，1987.

    [2]徐明曜，黄建华，李慧陵，等.有限群导引（下册）[M].北京：科学出版社，1999.

    [3] Suzuke M.Group theory I[M].New York：Springer-Verlag，1982.

    [4] Wang C Q，Wang D J，Xu M Y.On the normal Cayley Graphs of finite groups[J].Science in China（A），1998（28）：131-139.

    [5] Feng Y Q，Kwak J H，Automorphism W R J.groups of 4-valent connected Cayley graphs of p-groups[J].Chin Ann Math，2001（22B）：281-286.

    [6]化小会，冯衍全.8p阶5度对称图[J].北京交通大学学报，2011（03）：132-135，141.

    [7] Wang Changqun，Zhou ZhiYong.One-Regularity of 4-Valent and Normal Cayley Graphs of Dihedral Groups[J].Acta Mathematica Sinica，2006（03）：669-678.

    [8] Li Caiheng，Lou Bengong，Pan Jiangmin.Finite locally primitive abelian Cayley graphs[J].Science in China（Mathematics），2011（04）：845-854.

    [9]Wang C Q，Xu M Y.Nonnormal 1-regular and 4-valent Cayley Graphs of dihedral groups D2n[J].European J Combin，2006（27）：750-766.

    [10]陈松良，蒋启燕.关于108阶群的完全分类[J].郑州大学学报（理学版），2013（01）：10-14.

    [11]高锐敏，李巧利，王长群.一类点传递但边不传递的正则图及其覆盖图[J].数学的实践与认识，2014（19）：216-220.

    [12]Chris Godsil，Gordon Royle.Algerbraic Graph Theory[M].New York：Spinger，2004.

    [13]Gross J.L.，TuckerT.W..Generating all graph coverings by permutation voltage as Signment[J].Discrete Math，1977（18）：273-283.