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

1、設(shè)G是有限群，S(可以含G的單位元)是G的子集。Bi-Cayley圖BC(G，S)是一個(gè)二部圖，它的頂點(diǎn)集為G×{0，1}，邊集為{(g，0)(sg，1)：g∈G，s∈S}。顯然，BC(G，S)是|S|-正則圖。BC(G，S)是連通的當(dāng)且僅當(dāng)S_S生成G。在這篇論文中，我們考慮連通三正則BC(G，S)和對(duì)稱群上的BC(Sn，Tn)。設(shè)Sn=Sym(n)是集合{1，2，…，n}上的對(duì)稱群，Tn是由對(duì)稱群的單位元和所有對(duì)換構(gòu)成。因?yàn)門n-1

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