＊ 冒泡排序图的超带性

师海忠，乔韵璇

（1.西北师范大学 数学与信息科学学院，甘肃 兰州 730070；2.山西师范大学 数学与计算机科学学院，山西 临汾 041000）

＊冒泡排序图的超带性

师海忠1，乔韵璇2＊

（1.西北师范大学 数学与信息科学学院，甘肃 兰州 730070；2.山西师范大学 数学与计算机科学学院，山西 临汾 041000）

图G的k－路集C（u，v）是连接G中顶点u和v的k条内点不交的路的集合.图G的k－路集C（u，v）是一个k＊－路集如果连接顶点u和v的k条内点不交的路包含G中所有的顶点.一个二部图G是k＊－带的若G中任意两个属于不同二划分集的顶点之间存在k＊－路集.设κ（G）是图G的连通度.一个二部图是超带的若G是i＊－带的，1≤i≤κ（G）.n维冒泡排序图B n是二部图，是n－1正则的，有n！个顶点.在本文中，首先证明了Bn是（n－1）＊－带的，n≥5，然后得到n维冒泡排序图B n（n≠3）是超带的.

哈密尔顿；哈密尔顿带；冒泡排序图

0 引言

本文采用文献［5］中有关图论术语和记号.设G＝（V，E）是连通的简单无向图.G＝（V，E）表示顶点集为V，边集为E的图.如果（u，v）∈E，则两顶点u和v相邻.任一条路Q用＜v0，v1，v2，…，vk＞表示，vi∈G.路Q中包含的边的数目称为路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）表示顶点u和v之间的距离，即顶点u和v之间最短路的长度.图G中从顶点u到v顶点的一条路是哈密尔顿路，如果这条路包含G中所有顶点.图G是哈密尔顿连通的，如果G中任意不同的两点之间存在哈密尔顿路.图G的一个圈是哈密尔顿圈，如果这个圈经过G的每个顶点恰一次.

本文的组织结构如下：第二部分，给出了冒泡排序图的定义和基本性质；第三部分，证明了冒泡排序图Bn是超带的当且仅当n≠3.

1 预备知识

下面给出n维冒泡排序图的定义和它的一些基本性质.设n是一正整数，＜n＞＝｛1，2，…，n｝.

定义1［5］n维冒泡排序图B n的顶点集是由集合｛1，2，…，n｝的n！个置换所构成的.集合｛1，2，…，n｝的一个置换表示为x＝x1x2…x n，点x的邻点（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！个顶点，每个顶点的度为n－1.冒泡排序图Bn是二部图，Bn中的一部分顶点是奇置换.另一部分顶点是偶置换，在此用白顶点表示偶置换，黑顶点表示奇置换.

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

对1≤i≤n，Bn中顶点x的第i个数字用x［i］.例如，顶点x＝35 412；x［1］＝3，x［2］＝5，x［3］＝4，x［4］＝1，x［5］＝2.顶点x的四个邻点分别是：（x）1＝53 412，（x）2＝34 512，（x）3＝35 142，（x）4＝35 421.冒泡排序图Bn的一个重要性质就是它的可缩结构.固定i（1≤i≤n），子图是由顶点集｛x｜x［n］＝i｝构成的Bn的导出子图.由冒泡排序图的定义，同构于B n－1.Ei，j（Bn）表示子图Bn（i）与Bn（j）之间所有的连边.把（u）n－1称之为u的外邻点，如果（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＊－带的.

证明 因为B4是点可迁的，在此我们只需列出从点1234到B4中的任意一黑点的3＊－路集即可，如下：

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

证明 对于B1和B2，结论显然成立.因为B3是六个顶点构成的圈.所以B3不是1＊－带的.即B3不是超带的.由冒泡排序图Bn的性、定理1和定理3，B4是超带的.假设Bk是超带的，4≤k≤n－1.应用定理1和定理4，Bn是k＊－带的，k∈｛1，2，n－1｝.因此需要构建一Bn中连接白顶点u和顶点v的k＊－路集，3≤k≤n－2.假设Bn－1是k＊－带的，应用引理2，Bn中存在连接顶点u和顶点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－hsing.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

甘肃省自然科学基金（ZS991－A25－017－G）

师海忠（1963－ ），男，甘肃临洮人，博士，副教授，主要研究方向：组合优化，互连网络理论，图半群与图语言等.＊通讯作者：乔韵璇（1991－），女，山西忻州人，主要研究方向：图理论，组合优化.E－mail：niupan198507＠163.com

0253－2395（2012）04－0632－05