冒泡排序图的超带性  

Super Laceability of the Bubble Sort Graphs

作　　者：师海忠[1] 乔韵璇[2] 

机构地区：[1]西北师范大学数学与信息科学学院 [2]山西师范大学数学与计算机科学学院

出　　处：《山西大学学报（自然科学版）》2012年第4期632-636,共5页Journal of Shanxi University(Natural Science Edition)

基　　金：甘肃省自然科学基金(ZS991-A25-017-G)

摘　　要：图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维冒泡排序图Bn是二部图,是n-1正则的,有n!个顶点.在本文中,首先证明了Bn是(n-1)*-带的,n≥5,然后得到n维冒泡排序图Bn(n≠3)是超带的.The k-container C（u,v） of a graph G is a set of k-disjoint paths joining u to v.The k-container C（u,v） of a graph G is a k＊-container if it contains all the vertices of G.A bipartite graph G is k＊-laceable if there exist a k＊-container between any two vertices of different partite sets of G.Let κ（G） be the connectivity of G.A bipartite graph is super laceable if G is i＊-laceable for all 1≤i≤κ（G）.The n-dimensional bubble-sort graph Bn is bipartite,（n-1）-regular,and has n!vertices.We show that Bn is（n-1）＊-laceable if n≥5,then we also prove that n-dimensional bubble sort graph Bn is super laceable if and only if n≠3.

关 键 词：哈密尔顿 哈密尔顿带 冒泡排序图 

分 类 号：TP393[自动化与计算机技术—计算机应用技术] O157.5[自动化与计算机技术—计算机科学与技术]