由輪生成的Cayley 圖的廣義3 -連通度

張 燕， 馬木提·阿依古麗

（新疆大學 數學與系統科學學院，新疆 烏魯木齊830046）

1 引言及預備知識

令G ＝（V，E）表示點集為V（G）和邊集為E（G）的圖.任意一點v∈V（G），

NG（v）＝｛u∈V（G）＼｛v｝｜uv∈E（G）｝

表示v在G中的鄰集. v 在G 中的度，記為dG（v），其中dG（v）＝｜NG（v）｜. Δ（G）和δ（G）分別表示G的最大度和最小度.若Δ（G）＝δ（G）＝k，則稱G 是k-正則的.任意點x，y∈V（G），記（x，y）-路P ＝｛x ＝x0，x1，…，xk＝y｝，其起點是x，終點是y，內部點是x1，x2，…，xk-1.若路P上的兩點是連續的，則這兩點是相鄰的.一個長為1 的路是一個邊，簡記xy.若G中的2 條（x，y）-路P 和Q沒有公共內部點，則稱它們是內部不交的，也就是說，V（P）∩V（Q）＝｛x，y｝.若

則（X，Y）-路是一族由起點為x∈X，終點為y∈Y，且內部點既不屬于X，也不屬于Y 的內部不交路.特別地，若X ＝｛x｝，則（X，Y）-路是一族由起點為x，終點為Y中不同點的內部不交路.對于未提到的圖的理論符號和術語，參考文獻［1］.

傳統連通度κ（G）是圖G的點子集X的最小基數，使得G-X 是不連通的或平凡的.若κ（G）≥k，則圖G 是k -連通的.眾所周知，Whitney［2］提出了與連通度等價的定義.若S ＝｛u，v｝是V（G）中的任意一個2 元-子集，則κ（G）表示G 中內部不交的（u，v）-路的最大數目.作為傳統連通度的一個推廣，Chartrand等［3］在1984 年提出了廣義k -連通度.這個參數可以通過連接圖G中的任意k個點來衡量圖G的容錯性.令G是一個階為n的連通圖，S是圖G中任意一個k 個點的集合，其中k 是整數，且2≤k≤n，若S?V（T），則稱樹T是G的一個S-樹.令｛T1，T2，…，Tr｝是圖G的S-樹的集合，若

且

其中1≤i≠j≤r，則稱其是內部不交的.令κG（S）表示圖G中內部不交S-樹的最大數目，用κk（G）表示圖G的廣義k-連通度，其中

顯然G的廣義2 -連通度κ2（G）恰好是κ（G）.

近幾年，廣義k-連通度受到了一些關注，Li［4］證明了一般圖G是否存在k個內部不交的S-樹是NP-完全問題，其中S?V（G），｜S ｜＝k，且k是固定的整數.目前，已經有了關于廣義連通度的上界和下界的結果［5］.除此之外，還有一些關于某類圖的廣義k-連通度的結果，但大多是關于k ＝3 或4.例如，Li 等確定了卡氏積圖［6］、星圖［7］、冒泡排序圖［7］及由樹和圈生成的Cayley 圖的廣義3 -連通度［8］.Lin等［9］確定了超立方體的廣義4 -連通度等，其中由圈生成的Cayley 圖—修正冒泡排序圖MBn的廣義3 -連通度的結果如下：

定理1.1［8］κ3（MBn）＝n-1，其中n≥3.

在本文中，主要研究由輪生成的Cayley 圖WGn，并證明下面的結論：

定理1.2 κ3（WGn）＝2n-3，其中n≥4.

令Vn是由集合｛1，2，…，n｝生成的n！個不同置換的集合.令p ＝p1p2…pn是Vn中的一個置換，其中pi表示置換p 的第i 位.對換φi，j是一個交換已知置換的第i位和第j位的函數，其中1≤i ＜j≤n，且一般定義如下：已知p ＝p1p2…pn是Vn中的一個置換，則

Shi［10］提出了有關Cayley圖Cay（Sym（n），T）的概念，其中Sym（n）是在｛1，2，…，n｝上的對稱群，T是Sym（n）的對換集合. G（T）表示點集是｛1，2，…，n｝，邊集是｛ij ｜（ij）∈T｝的圖，稱G（T）為Cay（Sym（n），T）的生成圖.

若G（T）是一個單圈圖，UGn表示單圈-對換圖Cay（Sym（n），T）.特別地，若G（T）是一個圈，則稱UGn是修正冒泡排序圖MBn.圖1 和圖2 分別表示MB3和MB4.眾所周知，UGn是一個n -正則n-連通二部點傳遞圖.

圖1 由三角形生成的修正冒泡排序圖MB3Fig. 1 The modified bubble sort graph MB3 generated by a triangle

圖2 由C4生成的修正冒泡排序圖MB4Fig. 2 The modified bubble sort graph MB4 generated by C4

若G（T）是一個輪圖Wn，WGn表示輪-對換圖Cay（Sym（n），T），其中輪圖是由一個單點與一個（n-1）-圈上所有點相連形成的圖. W4和WG4如圖3 所示.從定義可知，WGn是一個（2n -2）-正則二部點傳遞圖［11］.

圖3 由輪圖W4生成的Cayley圖WG4Fig. 3 The Cayley graph WG4 generated by wheel graph W4

下面的引理將會用于定理1.2 的證明.

引理1.1［5］若存在2 個度為δ（G）的相鄰點，則κk（G）≤δ（G）-1，其中3≤k≤｜V（G）｜.

引理1.2［1］若G是一個k-連通圖，x是G中的任一點，Y?V＼｛x｝是至少有k個點的集合，則在G中存在k條內部不交且終點是Y中不同點的（x，Y）-路.

對每個i∈｛1，2，…，n-3｝，令