兩類Bi-Cayley圖的連通性.pdf

1、設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-1

2、Tn生成Sn，所以BC(Sn，Tn)連通。一個圖X稱為是上連通的，如果每一個最小割集都是一個點的點鄰集。類似地，一個圖X稱為是超連通的，如果對每一個最小割集C，都有X-C只有兩個連通分支，且其中一個連通分支為孤立點。在[8]中，王大猛和孟吉翔刻劃了上連通和超連通三次點傳遞圖。從這篇論文中受到啟發(fā)，我們將刻劃上連通和超連通的三正則BC(G，S)和BC(Sn，Tn).下面是我們的主要結果： 1.連通的三正則BC(G，S)是上連通的。