摘 要： 本文通过定义的运算“*”，简要讨论了集合τ*τ={（τ，x）*（τ，y）|x∈V，y∈V}的计数问题.其中：V）=V∪V，E） =E∪E∪{（x，y）}。研究得到，在运算“*”下：若τ，τ是两棵同阶不同构简单无向树，则|τ*τ={（τ，x）*（τ，y）|x∈V，y∈V}|=|V/Autτ| · |V/Autτ|.

关键词： 树 自同构群 点轨道

对于一般的图，可以通过自同构群的概念将群与图联系起来，而这正是图论的一个充满活力的新分支.在Springer出版的《Algebraic Graph Theory》一书中有比较系统的介绍.这其中研究得比较多的对象是通过群构造的凯莱图，还有一些特殊图，如正则图、树、线图等.在文献[1]中讨论了双Cayley图的自同构群.在文献[2]、[3]、[4]中讨论了Cayley图的Hamilton性.还有的研究方向是讨论图的不同性质如何通过其自同构群反应，这里面有一些重要而没有解决的猜想，如“顶点传递的简单连通图，则一定存在Hamilton路”.在Jean-Pierre Serre的著作《Trees》中又讨论了树，其中第一章第六节研究了树在其任意的自同构作用下的不动点.在学习《Trees》时，受到启发，开始研究由两棵树生成新树时，对称群有什么样的影响.并进行关于简单树的一类计数问题的讨论.

本文中讨论的是只有有限个顶点的简单无向树.

τ=（V，E）表示图.V为τ的顶点集，E为τ的边集.τ*τ={（τ，x）*（τ，y）|x∈V，y∈V}.其中：V=V∪V，E=E∪E∪{（x，y）}，设α是V→V的一一映射，且满足？坌（x，y）∈E，（α（x），α（y））∈E和？坌（x，y）∈E，（α（x），α（y））∈E，称α为图τ上的一个自同构.由τ上的所有自同构构成的集合记作Autτ，且Autτ构成一个群，我们称之为τ的自同构群.

x∈V，A表示a在Autτ作用下的点轨道类.τ=Γ

引理1给定图τ=（V，E），τ=（V，E），若f为τ→τ的同构映射，则？坌x∈V，？埚x∈V f（x）=x.

证明：由图之间同构的定义，引理显然成立.

引理2 给4个定简单无向的连通树τ=（V，E），τ=（V，E），τ=（V，E），τ=（V，E），V∩V=？覬（i，j∈{1，2，3，4}，i≠j），取a∈V，b∈V，c∈V，d∈V，设|V|=|V|=|V|=|V|.若f为（τ，a）*（τ，b）→ （τ，c）*（τ，d）的同构映射，则有：

（1）f（（a，b））=（c，d）.

（2）τ≌τ，τ≌τ且f（a）=c，f（b）=d.或者τ≌τ，τ≌τ且f（a）=d，f（b）=c.

证明：（1）设f为（τ，a）*（τ，b）→（τ，c）*（τ，d）的同构映射，假设f（（a，b））=（m，n），（（a，b）∈E，（b，z）∈E）（其中（c，d）≠（m，n））.由树（τ，a）*（τ，b）的定义，可设当树（τ，a）*（τ，b）抹去边（a，b）时，得到两个连通的子图分别为τ，τ.因为f为（τ，a）*（τ，b）→（τ，c）*（τ，d）的同构映射，且f（（a，b））=（m，n）.所以当（τ，c）*（τ，d）抹去（m，n）时，也得到两个连通的子图，我们分别设为树图τ，τ，其中m∈V，n∈V，且由同构的定义可得|V|= |V|.因为（c，d）≠（m，n），所以有（c，d）∈E或（c，d）∈E，假设（c，d）∈E，由树（τ，c）*（τ，d）的定义，可设当树（τ，c）*（τ，d）抹去边（c，d）时，得到两个连通的子图分别为τ，τ，我们有V∩V≠？覬且V∩V≠？覬，同时能得到V∩V≠？覬且V∩V≠？覬.因为树（τ，c）*（τ，d）的子图τ，τ，τ，τ都是连通的子图，当（m，n）∈E时，我们构造树τ的一条连通的道路Γ（v∈τ，v∈τ且v∈τ，v∈τ），当（m，n）∈E时，我们构造树τ的一条连通的道路Γ（v∈τ，v∈τ且v∈τ，v∈τ），所以可以得到树（τ，c）*（τ，d）的一条连通道路Γ，且边（m，n）不属于这条连通的道路，因为当（τ，c）*（τ，d）抹去（m，n）时，得到两个连通的子图，我们分别设为树τ，τ，即树（τ，c）*（τ，d）存在一条由v→v的连通道路Γ′，且（m，n）∈E.这将导致树（τ，c）*（τ，d）存在回路，同理当（c，d）∈E，也会导致树（τ，c）*（τ，d）存在回路，这都将与树的定义矛盾.所以若f为（τ，a）*（τ，b）→（τ，c）*（τ，d）的同构映射，则f（（a，b））=（c，d）.

（2）由（1）可得f为（τ，a）*（τ，b）→（τ，c）*（τ，d）的同构映射，则f（a）=c，f（b）=d或者f（a）=d，f（b）=c.当f（a）=c，f（b）=d时，假设f（V）≠V，则有f（V）∩V≠？覬且f（V）∩V≠？覬.所以当树（τ，a）*（τ，b）抹去顶点，得到至少两个连通子图，这与树（τ，c）*（τ，d）的定义矛盾（因为（τ，c）*（τ，d）抹去顶点集V生成的是一个连通子图，由同构映射的定义可知树（τ，a）*（τ，b）抹去顶点集V生成的是一个连通子图），所以f（V）=V，因为f为（τ，a）*（τ，b）→（τ，c）*（τ，d）的同构映射，所以f（V）=V.由同构映射的定义得τ≌τ，τ≌τ且f（a）=c，f（b）=d.

同理当f（a）=d，f（b）=c，我们也能得到τ≌τ，τ≌τ且f（a）=d，f（b）=c所以定理得证.

引理3 假设|V|=|V|=|V|，且（τ，a）*（τ，y）≌（τ，b）*（τ，z）.则有τ≌τ.

证明：设f：（τ，a）*（τ，y）→（τ，b）*（τ，z）的同构映射，由引理2的（2）有τ≌τ，τ≌τ，且a→b，y→z.或者τ≌τ，τ≌τ且a→z，y→b.当有τ≌τ，τ≌τ且a→b，y→z，定理得证.当τ≌τ，τ≌τ且a→z，y→b，显然有τ≌τ.

引理4 假设|V|=|V|=|V|，且a，b∈V，y∈V.当在图τ=（V，E）中有A=A时，则在（τ，a）*（τ，y）≌（τ，b）*（τ，y）

证明：假设由A、A的定义可知？埚f∈Autτ， f（a）=b，定义f（x）=f（x），x∈Vx，x∈V，显然可得，f是Aut（τ，a）*（τ，y）→（τ，b）*（τ，y）的同构.

引理5 假设|V|=|V|=|V|，且a，b∈V，y∈V，当（τ，a）*（τ，y）≌（τ，b）*（τ，y），则有A=A.

证明：设f为（τ，a）*（τ，y）≌（τ，b）*（τ，y）的同构映射，由引理2的（2）有τ≌τ，τ≌τ且a→b，y→y.或者τ≌τ，τ≌τ，且a→y，y→b.当有τ≌τ，τ≌τ，且a→b，y→y，显然有A=A.当τ≌τ，τ≌τ，且a→y，y→b，可以得到τ≌τ且a→b，所以有A=A.所以引理得证.

引理6 假设|V|=|V|，取a，b∈V，y，z∈V，若τ不同构τ.则（τ，a）*（τ，y）≌（τ，b）*（τ，z）当且仅当A=A，A=A.

证明：充分性：设f为（τ，a）*（τ，y）≌（τ，b）*（τ，y）的同构映射，由引理2的（2）有τ≌τ，τ≌τ且a→b，y→y.或者τ≌τ，τ≌τ且a→y，y→b.因为τ不同构τ，所以只有τ≌τ，τ≌τ且a→b，y→y是成立的，显然在树τ中有A=A，又由引理5得到在树τ中有A=A.

必要性：若有A=A，A=A，由引理4显然可得，（τ，a）*（τ，y）≌（τ，b）*（τ，z）.

定理1 假设|V|=|V|，若τ，τ不同构，则|τ*τ={（τ，x）*（τ，y）|x∈V，y∈V}|=|V/Autτ|·|V/Autτ|

证明：由引理6有（τ，a）*（τ，y）≌（τ，b）*（τ，z）当且仅当A=A，A=A.所以有|τ*τ={（τ，x）*（τ，y）|x∈V，y∈V}|=|V/Autτ|·|V/Autτ|.

引理7 假设|V|=|V|，取a，b∈V，y，z∈V.若τ≌τ，则（τ，a）*（τ，y）≌（τ，b）*（τ，z）当且仅当存在f为τ→τ的同构映射使得f（a）=z，f（b）=y，或A=A，A=A.

证明：充分性：若τ≌τ，当在树τ中A=A，又由引理5可得A=A，所以A=A，A=A.当A≠A，因为|V|=|V|，由（τ，a）*（τ，y）≌（τ，b）*（τ，z）的定义，若设f为（τ，a）*（τ，y）→（τ，b）*（τ，z）的同构映射，由引理2的（2）有τ≌τ，τ≌τ且a→b，y→z，.或者τ≌τ，τ≌τ且a→z，y→b.因为A≠A，所以只能有τ≌τ，τ≌τ且a→z，y→b.所以有f（a）=z，f（b）=y.

必要性：若有A=A，A=A，由引理4可得（τ，a）*（τ，y）≌（τ，b）*（τ，z）.若存在f为τ→τ的同构映射使得f（a）=z，f（b）=y，显然有（τ，a）*（τ，y）≌（τ，b）*（τ，z）.

推论1 假设|V|=|V|，若τ≌τ，则|τ*τ={（τ，x）*（τ，y）|x∈V，y∈V}|=.

证明：若（τ，a）*（τ，y）与（τ，b）*（τ，z）同构，由引理7可知存在两种情况，（1）A=A，A=A时.（2）A≠A时，存在f为τ→τ的同构映射使得f（a）=z，f（b）=y.在只考虑（1）的情况下，|τ*τ={（τ，x）*（τ，y）|x∈V，y∈V}|=|V/Autτ|·|V/Autτ|.当A≠A时，在情况（1）下的计数会被重复一次.所以可以得|τ*τ={（τ，x）*（τ，y）|x∈V，y∈V}|=.

参考文献：

[1]路在平.On the automorphisms groups of BiCayley Graphs [J].北京大学学报（自然科学版），2003，36.

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

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

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

[5]Chris Godsil，Gordsil Royle.Algebraic Graph Theory[M].世界图书出版公司，2004：5-6.

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