论文部分内容阅读
Cayley图是一类重要的点传递图，并且每一个点传递图都可以看作是一个Cayley图的收缩核[4]。在这篇论文中，我们考虑对称群上的一些特殊Cayley图。设S=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={(1i)，(jj+1)|2≤i≤m，m≤j≤n-1}(4≤m≤n-1)，
T4={(12i)，(2i2i+1)|1≤i≤m}(m≥3).我们分别定义Cayley图X(Sn，T3)和X(S2m+1，T4)为星路图SPn(m)和扩展星图ESSTm+1。因为T3和T4的对换图都是树，所以T3生成Sn，T4生成S2m+1，星路图SPn(m)和扩展星图EST2m+1都是连通的。
对一个图X，把它的自同构群记为Aut(X)。通常要确定一个图的自同构群是比较困难的，即使对于Cayley图也是如此。在[8]中，作者已经给出了星图和bubble-sort图的全自同构群。受到这些结果的启发，我们将给出星路图SPn(m)和扩展星图EST2m+1的全自同构群。关于它们的其它一些性质在这篇论文中也将被考虑。下