【摘要】 设G=(V,E)是一个图,F V(G)是一个点子集.称F为G的一个k-超点割,如果G F不再连通且G F的每一个连通分支都至少有k+1个点.图G的k-超点连通度,记作κk(G),是图G的最小k-超点割的基数,它是图的容错性的一种精化了的度量.本文研究修正泡序图MBn的κ2,并证明对于n≥4,κ2(MBn)=3n 5.更多还原

【Abstract】 For a graph G =(V,E),a subset F V(G) is called a k-extra vertex-cut of G if G F is disconnected and each connected component of G F has at least k + 1 vertices.The k-extra vertex-connectivity of G,denoted by κ k(G),is the cardinality of the minimum k-extra vertex-cut of G,which is a refined measure of the fault tolerance of the graph.In this work,we study κ 2 for modified bubble sort graph MB n.We prove that κ 2(MB n) = 3n 5 for n ≥ 4.更多还原