一类Cayley图的可扩性

摘要

Let Sn be the symmetric group. Let 〈n〉={1,2,…,n}, B* denote the set of all transpositions for Sn and BB*. The transposition graph Wn with respect to B is defined by V(Wn)=〈n〉, E(Wn)={[uv]:(uv)∈B}. A transposition graph is called a transposition tree Tn if Wn is a tree. Tn is a minimal generating set of Sn. In this paper, we study the Cayley graph Cay(Sn, Tn). It is obtained that Cay(Sn,Tn) is (n-2)-extendable, i.e., the extensibility of Cay(Sn,Tn) is maximum.%设Sn是那个对称群. 让〈n〉={1,2,…,n}, B*表示Sn中所有对换的集合和BB*. 关于B的对换图Wn被定义为V(Wn)=〈n〉, E(Wn)={[uv]:(uv)∈B}. 如果Wn是一棵树,则这个对换图称为一棵对换树Tn. Tn是Sn的一个极小生成集. 在这篇文章里,我们研究了Cayley图Cay(Sn, Tn)的性质. 证明了Cay(Sn, Tn)是(n-2)-可扩的,即,Cay(Sn, Tn)的可扩性达到最大.