星路图和扩展星图的自同构群

论文摘要

Cayley图是一类重要的点传递图,并且每一个点传递图都可以看作是一个Cayley图的收缩核[4]。在这篇论文中,我们考虑对称群上的一些特殊Cayley图。设Sn=Sym（n）是集合{1,2,…,n}上的对称群,T是由对称群Sym（n）中的一些对换构成的集合。Cayley图X（Sn,T）是连通的当且仅当T是Sn的生成集合。T的对换图是顶点集为{1,2,…,n}的图T,T中的两个点i和j相邻当且仅当（ij）∈T。我们在[1]中可知T是Sn的极小生成集当且仅当它的对换图是树。设 T3={（1 i）,（j j+1）|2≤i≤m,m≤j≤n-1}（4≤m≤n-1）, T4={（1 2i）),（2i 2i+1）|1≤i≤m}（m≥3）。我们分别定义Cayley图X（Sn,T3）和X(S2m+1,T4)为星路图SPn（m）和扩展星图EST2m+1。因为T3和T4的对换图都是树,所以T3生成Sn,T4生成S2m+1,星路图SPn（m）和扩展星图EST2m+1都是连通的。 对一个图X,把它的自同构群记为Aut（X）。通常要确定一个图的自同构群是比较困难的,即使对于Cayley图也是如此。在[8]中,作者已经给出了星图和bubble-sort图的全自同构群。受到这些结果的启发,我们将给出星路图SPn（m）和扩展星图EST2m+1的全自同构群。关于它们的其它一些性质在这篇论文中也将被考虑。下面是我们的主要结果: 1.Aut（SPn（m））≌Sm-2·Sn2.Aut(EST2m+1)≌Sm·S2m+13.星路图和扩展星图都不是距离正则的,因此也都不是距离传递的。

论文目录

• Chinese abstract
• English abstract
• 1. Introduction
• 2. Some Preliminaries
• 3. Automorphism Group of Star-path Graphs and Extended-star Graphs
• 4. Some Properties of Star-path Graphs and Extended-star Graphs
• 5. References
• 6. Acknowledgement