＊ 冒泡排序圖的超帶性

師海忠，喬韻璇

（1.西北師范大學(xué) 數(shù)學(xué)與信息科學(xué)學(xué)院，甘肅 蘭州 730070；2.山西師范大學(xué) 數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院，山西 臨汾 041000）

＊冒泡排序圖的超帶性

師海忠1，喬韻璇2＊

（1.西北師范大學(xué) 數(shù)學(xué)與信息科學(xué)學(xué)院，甘肅 蘭州 730070；2.山西師范大學(xué) 數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院，山西 臨汾 041000）

圖G的k－路集C（u，v）是連接G中頂點(diǎn)u和v的k條內(nèi)點(diǎn)不交的路的集合.圖G的k－路集C（u，v）是一個(gè)k＊－路集如果連接頂點(diǎn)u和v的k條內(nèi)點(diǎn)不交的路包含G中所有的頂點(diǎn).一個(gè)二部圖G是k＊－帶的若G中任意兩個(gè)屬于不同二劃分集的頂點(diǎn)之間存在k＊－路集.設(shè)κ（G）是圖G的連通度.一個(gè)二部圖是超帶的若G是i＊－帶的，1≤i≤κ（G）.n維冒泡排序圖B n是二部圖，是n－1正則的，有n！個(gè)頂點(diǎn).在本文中，首先證明了Bn是（n－1）＊－帶的，n≥5，然后得到n維冒泡排序圖B n（n≠3）是超帶的.

哈密爾頓；哈密爾頓帶；冒泡排序圖

0 引言

本文采用文獻(xiàn)［5］中有關(guān)圖論術(shù)語和記號(hào).設(shè)G＝（V，E）是連通的簡單無向圖.G＝（V，E）表示頂點(diǎn)集為V，邊集為E的圖.如果（u，v）∈E，則兩頂點(diǎn)u和v相鄰.任一條路Q用＜v0，v1，v2，…，vk＞表示，vi∈G.路Q中包含的邊的數(shù)目稱為路Q的長度，記為l（Q）.把路＜v0，v1，v2，…，v k＞寫為＜v0，Q1，vi，vi＋1，…，vj，Q2，vt，…，vk＞.其中Q1是路＜v0，v1，v2，…，vi＞，Q2是路＜v j，v j＋1，…，vt＞.用d（u，v）表示頂點(diǎn)u和v之間的距離，即頂點(diǎn)u和v之間最短路的長度.圖G中從頂點(diǎn)u到v頂點(diǎn)的一條路是哈密爾頓路，如果這條路包含G中所有頂點(diǎn).圖G是哈密爾頓連通的，如果G中任意不同的兩點(diǎn)之間存在哈密爾頓路.圖G的一個(gè)圈是哈密爾頓圈，如果這個(gè)圈經(jīng)過G的每個(gè)頂點(diǎn)恰一次.

本文的組織結(jié)構(gòu)如下：第二部分，給出了冒泡排序圖的定義和基本性質(zhì)；第三部分，證明了冒泡排序圖Bn是超帶的當(dāng)且僅當(dāng)n≠3.

1 預(yù)備知識(shí)

下面給出n維冒泡排序圖的定義和它的一些基本性質(zhì).設(shè)n是一正整數(shù)，＜n＞＝｛1，2，…，n｝.

定義1［5］n維冒泡排序圖B n的頂點(diǎn)集是由集合｛1，2，…，n｝的n！個(gè)置換所構(gòu)成的.集合｛1，2，…，n｝的一個(gè)置換表示為x＝x1x2…x n，點(diǎn)x的鄰點(diǎn)（x）i＝x1…x i－1x i＋1x ix i＋2…x n，x i∈＜n＞，1≤i≤n－1.B2，B3和B4如下圖1所示：Bn是二部圖，它有n！個(gè)頂點(diǎn)，每個(gè)頂點(diǎn)的度為n－1.冒泡排序圖Bn是二部圖，Bn中的一部分頂點(diǎn)是奇置換.另一部分頂點(diǎn)是偶置換，在此用白頂點(diǎn)表示偶置換，黑頂點(diǎn)表示奇置換.

圖1 冒泡排序圖B 2，B 3，B 4Fig.1 Bubble sort graph B 2，B 3，B 4

對(duì)1≤i≤n，Bn中頂點(diǎn)x的第i個(gè)數(shù)字用x［i］.例如，頂點(diǎn)x＝35 412；x［1］＝3，x［2］＝5，x［3］＝4，x［4］＝1，x［5］＝2.頂點(diǎn)x的四個(gè)鄰點(diǎn)分別是：（x）1＝53 412，（x）2＝34 512，（x）3＝35 142，（x）4＝35 421.冒泡排序圖Bn的一個(gè)重要性質(zhì)就是它的可縮結(jié)構(gòu).固定i（1≤i≤n），子圖是由頂點(diǎn)集｛x｜x［n］＝i｝構(gòu)成的Bn的導(dǎo)出子圖.由冒泡排序圖的定義，同構(gòu)于B n－1.Ei，j（Bn）表示子圖Bn（i）與Bn（j）之間所有的連邊.把（u）n－1稱之為u的外鄰點(diǎn)，如果（u）n－1?Bn（i），u∈Bn（i）且（u）n－1與u相鄰.

2 冒泡排序圖的超帶性

定理1［5］冒泡排序圖Bn是哈密爾頓帶的，n≥4.

定理2［5］Bn是超哈密爾頓帶的，n≥4.

定理3B4是3＊－帶的.

證明 因?yàn)锽4是點(diǎn)可遷的，在此我們只需列出從點(diǎn)1234到B4中的任意一黑點(diǎn)的3＊－路集即可，如下：

定理5 冒泡排序圖Bn是超帶的，n≠3.

證明 對(duì)于B1和B2，結(jié)論顯然成立.因?yàn)锽3是六個(gè)頂點(diǎn)構(gòu)成的圈.所以B3不是1＊－帶的.即B3不是超帶的.由冒泡排序圖Bn的性、定理1和定理3，B4是超帶的.假設(shè)Bk是超帶的，4≤k≤n－1.應(yīng)用定理1和定理4，Bn是k＊－帶的，k∈｛1，2，n－1｝.因此需要構(gòu)建一Bn中連接白頂點(diǎn)u和頂點(diǎn)v的k＊－路集，3≤k≤n－2.假設(shè)Bn－1是k＊－帶的，應(yīng)用引理2，Bn中存在連接頂點(diǎn)u和頂點(diǎn)v的k＊－路集.

［1］ Akers S B，Krishnamurthy B.A Group－theoretic Model for Symmetric Interconnection Networks［J］.IEEETransactions onComputers，1989，38（4）：555－565.

［2］ Lakshmivarahan S，Jwo J S，Dhall S.Symmetric in Interconnection Networks Based on Cayley Graph of Permutation Groups：A Survey［J］.ParallelComputing，1993（19）：361－407.

［3］ Kaneko K，Suzuki Y.Node－to－node Internally Disjoint Paths Problem in Bubble Sort Graphs［C］／／Proceeding of the 10th IEEE Pacific Rim International Symposium on Dependable Computing，2004：173－182.

［4］ Yosuke Kikuchi，Toru Araki.Edge－bipancyclicity and Edge－fault－tolerant Bipancyclicity of Bubble－sort Graphs［J］.InformationPricessingLetters，2006（100）：52－59.

［5］ Toru Araki，Yosuke Kikuchi.Hamiltonian Laceability of Bubble－sort Graphs with Edge Faults［J］.InformationSciences，2007（177）：2679－2691.

［6］ Lun－Min Shih Tan，J J M.Fault－Tolerant Maximal Local－Connectivity on the Bubble－Sort Graphs［C］／／Information Technology：New Generations，2009.ITNG’09.Sixth International Conference on，2009：564－569.

［7］ Menger K.Zur Allgemeinen Kurventheorie［J］.Fundamenta，1927（10）：95－115.

［8］ Shi Hai－zhong，Niu Pan－feng，Lu Jian－bo.One Conjecture of Bubble－sort Graphs［J］.InformationPricessingLetters，2011（111）：926－929.

［9］ Bondy J A，Murty U S R.Graph Theory［M］.London：Spring，2008.7.

［10］ Lin Cheng－kuan，Huang Hua－Ming，Hsu Lih－h(huán)sing.The Super Connectivity of the Pancake Graphs and the Super Laceability of the Star Graphs［J］.TheoreticalComputerScience，2005（339）：257－271.

［11］ Chieh－Feng Chiang，Jimmy J M Tan.Strong Menger Connectivity on the Bubble－sort Graphs［C］.International Computer Symposium，2008.

［12］ Yasuto Suzuchi，Keiichi kaneko，An Algorithm for Disjioint Paths in Bubble－sort Graphs［J］.SystemsandComputerin Japan，2006（37）：751－756.

［13］ Yasuto Suzuki，Keiichi Kaneko.The Container Problem in Bubble－Sort Graphs［C］／／IEICE TRANS.INE＆.SYST.VOL.E91－D，NO.4APRIL，2008：1003－1009.

［14］ Yeh C H，Vararigos E A.Macro－star networks－Efficient low－degree Alternatives to star Graphs［J］.IEEETrans.ParallelDistribSyst，1998（10）：987－1003.

Super Laceability of the Bubble Sort Graphs

SHI Hai－zhong1，QIAO Yun－xuan2
（1.CollegeofMathematicsandInformationScience，NorthwestNormalUniversity，Lanzhou730070，China2.CollegeofMathematicsandComputerScience，ShanxiNormalUniversity，Linfen041000，China）

Thek－containerC（u，v）of a graphGis a set ofk－disjoint paths joiningutov.Thek－containerC（u，v）of a graphGis ak＊－container if it contains all the vertices ofG.A bipartite graphGisk＊－laceable if there exist ak＊－container between any two vertices of different partite sets ofG.Letκ（G）be the connectivity ofG.A bipartite graph is super laceable ifGisi＊－laceable for all 1≤i≤κ（G）.Then－dimensional bubble－sort graphBnis bipartite，（n－1）－regular，and hasn！vertices.We show thatBnis（n－1）＊－laceable ifn≥5，then we also prove thatn－dimensional bubble sort graphBnis super laceable if and only ifn≠3.

Hamiltonian；Hamiltonian laceable；the bubble sort graphs

TP393；O157.5

A

2012－05－13；

2012－08－30

甘肅省自然科學(xué)基金（ZS991－A25－017－G）

師海忠（1963－ ），男，甘肅臨洮人，博士，副教授，主要研究方向：組合優(yōu)化，互連網(wǎng)絡(luò)理論，圖半群與圖語言等.＊通訊作者：喬韻璇（1991－），女，山西忻州人，主要研究方向：圖理論，組合優(yōu)化.E－mail：niupan198507＠163.com

0253－2395（2012）04－0632－05