论文部分内容阅读
设G是有限群,S(可以含G的单位元)是G的子集。Bi-Cayley图BC(G,S)是一个二部图,它的顶点集为G×{0,1},边集为{(g,0)(sg,1):g∈G,s∈S}。显然,BC(G,S)是|S|-正则图。BC(G,S)是连通的当且仅当S_S生成G。在这篇论文中,我们考虑连通三正则BC(G,S)和对称群上的BC(Sn,Tn)。设Sn=Sym(n)是集合{1,2,…,n}上的对称群,Tn是由对称群的单位元和所有对换构成。因为Tn-1Tn生成Sn,所以BC(Sn,Tn)连通。一个图X称为是上连通的,如果每一个最小割集都是一个点的点邻集。类似地,一个图X称为是超连通的,如果对每一个最小割集C,都有X-C只有两个连通分支,且其中一个连通分支为孤立点。在[8]中,王大猛和孟吉翔刻划了上连通和超连通三次点传递图。从这篇论文中受到启发,我们将刻划上连通和超连通的三正则BC(G,S)和BC(Sn,Tn).下面是我们的主要结果:
1.连通的三正则BC(G,S)是上连通的。
2.连通的三正则BC(G,S)是超连通的当且仅当BC(G,S)()K3,3。
3.BC(Sn,Tn)是超连通的。