树的强自同态幺半群的一些特征

摘 要： 给定图τ=（V，E）为只有有限个顶点的无向，简单树（文中涉及的树都满足这个条件）.设τ的所有强自同态映射组成的半群为树图τ的强自同态幺半群，记作sEndτ.通过树的特征研究了树的强自同态幺半群的特征，得到结论：若τ′为τ的连通子图，则sEndτ′同构于sEndτ的子半群.

关键词： 自同态幺半群 连通子图 子半群 右理想

有限单群的分类经过群论工作者长达150年的努力，已于上个世纪八十年代完成[1].学者们最终证明，有限单群共有十八个无限族和二十六个零散单群.单群分类完成后，Gorenstein提到了群论研究的几个发展方向：新领域的出现（比如，对可解群的研究更加深入），图的研究及在分类过程中提出的研究方法的应用等.

通过阅读与思考，发现其中研究得比较多的对象是通过群构造的凯莱图（均是点传递的图，即图在其自同构群作用下只有一条顶点轨道），还有一些特殊图，如正则图线图等.例如：在文献[8]中，讨论了双Cayley图的自同构群.在文[2]，[3]，[4]讨论了Cayley图的Hamilton性.还有的讨论点传递图的Hamilton性的文章，见文献[5][6].

文章尝试讨论图的自同态幺半群与图的结构之间的关系.因为一般图形的研究难度较大，于是主要讨论简单树强自同态幺半群，最后得到：树的每个连通子图的强自同态幺半群均同构与树的强自同态幺半群的子半群；树的强自同态幺半群的极大右理想对应树的极大连通子图.

文章未作特殊说明处，均讨论有限个顶点的简单无向树.

τ表示一棵树.用V 为树τ的顶点集，E 为树τ的边集.

给定两棵树τ′，τ.设α是V →V 的一个映射，且满足？坌x，y∈V ，若（x，y）∈E，则（α（x），α（y））∈E 且？坌m，n∈V ，（m，n）∈E ，蕴含（m，n）的原象属于E ，称α为图τ到τ′上的一个强同态.

树τ的强自同态半群：τ到自身的所有强同态组成的集合，记作sEnd（τ）.

α（τ）表示同态映射α作用于树τ得到的新树，记为α（τ）=τ .

其中V =τ（V ），E =τ（E ）.

引理1 树τ的强自同态半群sEnd（τ）为幺半群.

证明：设e是Autτ的单位元，由定义可知e∈sEnd（τ），显然有？坌α∈sEndτ，αe=eα所以引理得证.

引理2 设α∈sEndτ，令α（τ）=τ ，则τ 为τ的连通子图.

证明：由定义易知，？坌x，y∈V ，若（x，y）∈E ，则（α（x），α（y））∈E 有τ 连通图.又因为V ？哿V ，？坌m，n∈V ，（m，n）∈E 蕴含（m，n）的原象属于E ，

则显然有τ 为τ的子图.所以τ 为τ的连通子图.

引理 3 设τ的阶是n（n≥2），若τ 为τ的n-1阶连通子图，则？埚α∈sEndτ，使得α（τ）=τ ，α（τ ）=τ .

证明：易证τ 为τ的n-1阶连通子图，等价于τ去掉的是一片叶子.当n=2时，引理显然成立.当n≥3时，设τ 是去掉了叶子v 得到，令v 是与v 相邻的（即（v ，v ）∈E ），v 是与v 相邻且v ≠v .构造α，令α（v ）=v ？摇？摇i≠1v ？摇？摇i=1，由sEnd（τ）的定义易知α∈sEndτ.引理得证.

推论1设τ的阶是n（n≥2），若τ 为τ的k（k=1，2…，n-1，n）阶连通子图，则？埚α∈sEndτ，使得α（τ）=τ ，且α（τ ）=τ .

证明：当k=n时，α∈Autτ，显然有α∈sEndτ.当k=n-1时，由引理3结论可得证.当k=n-2时，可得存在τ 为τ的n-1阶连通子图且τ 为τ 的n-2阶连通子图，由引理3，？埚β∈sEndτ，使β（τ）=τ ，α（τ ）=τ .同理得，？埚？掊∈sEndτ ，使？掊（τ ）=τ ，？掊（τ ）=τ .则α=？掊·β.由定义易知α∈sEndτ.推论1得证.

定理1若τ′为τ的连通子图，则sEndτ′同构于sEndτ的子半群.

证明：由推论1知？埚α∈sEndτ，使得α（τ）=τ′，α（τ′）=τ′.？坌β∈sEndτ′，令β′=αβ，S ={αβ|β∈sEndτ′}.一、若？坌β ，β ∈sEndτ′，β ≠β ，则有αβ ≠αβ ，所以sEndτ′与S ={αβ|β∈sEndτ′}之间一一对应.二、由（αβ ）·（αβ ）=αβ αβ =α（β α）β =α（β β ），得sEndτ′与S ={αβ|β∈sEndτ′}之间同态关系α：β→αβ.由一、二可得sEndτ′同构于S ={αβ|β∈sEndτ′}.易知S ={αβ|β∈sEndτ′}？哿sEndτ，所以sEndτ′同构于sEndτ的子半群.

将已知条件中的树换成有限阶的有向简单树时则不一定出现定理一的情况.

例子1，构造有限阶的简单有向树τ=（V，E），如图1.再构造其子图τ′=（V′，E′），如图2.

由图1可知，sEndτ为{e，α}，α（v ）=v ，i≠8v ，i=8，i=1，2，…，9.由图2可得Autτ′=S ？哿sEndτ′.易知，sEndτ′不可能同构于sEndτ的子半群.

进一步思考，还有什么样的图能有定理一这样的性质呢？通过研究得到1个简单的猜想.

当一个有限阶的简单有向图有一个圈时，则不一定有定理一的性质.例如：构造有限阶的简单无向图G=（V，E），其中v={v ，v ，v }，E={（v ，v ），（v ，v ），（v ，v ）}，如图3.易知，图4G′=（V′，E′）为G=（V，E）的连通子图.我们有AutG=S ，但是AytG′=S .显然图G与G′有不同自同构群.又因为sEndG=S ，所以sEndG′不可能同构于sEndG的子半群.

因此，产生一个猜想，只有当限阶的简单有向图G=（V，E）是一棵树时，才会有定理一的结果.

参考文献：

[1]D.Gorenstein，Finite Simple Groups，Harper and Row，NewYork，1968.

[2]路在平.双Cayley图的自同构群[J].北京大学学报（自然科学版），2003，39（1）：1-5.

[3]Meng Jixiang，Huang qiongxiang.Almost all Cayley Graphs Are Hamiltonian[J].Acta Mathematica Sinica，1996，12：151-155.

[4]Li Haizhu，Wang Jianfang，Sun Liang.Hamiltonian decomposition of Cayley graphs of ordersp2 andpq [J].Acta Mathematicae Applicatae Sinica，2000，16：78-86.

[5]S.J.Curran，J.A.Gallian.Hamiltonian cycles and paths in Cayley graphs and digraphs—a survey，Discrete Math，1996 （156）：1-18.

[6]D.Marusic，Hamiltonian cycles in vertex-symmetric graphs of order 2p^2，Discrete Math，1987（66）：169-174.

[7]祝富洋，游泰杰，徐波.树在其自同构群下的点轨道集的特征[J].贵州师范大学学报（自然科学版），2013.