The m-Component Connectivity of Leaf-Sort Graphs

Connectivity plays an important role in measuring the fault tolerance of interconnection networks. As a special class of connectivity, m-component connectivity is a natural generalization of the traditional connectivity of graphs defined in terms of the minimum vertex cut. Moreover, it is a more advanced metric to assess the fault tolerance of a graph G. Let G=(V(G),E(G)) be a non-complete graph. A subset F(F subset of V(G)) is called an m-component cut of G, if G-F is disconnected and has at least m components (m >= 2). The m-component connectivity of G, denoted by c kappa(m)(G), is the cardinality of the minimum m-component cut. Let CFn denote the n-dimensional leaf-sort graph. Since many structures do not exist in leaf-sort graphs, many of their properties have not been studied. In this paper, we show that c kappa(3)(CFn)=3n-6 (n is odd) and c kappa(3)(CFn)=3n-7 (n is even) for n >= 3; c kappa(4)(CFn)=9n-21/2 (n is odd) and c kappa(4)(CFn)=9n-24/2 (n is even) for n >= 4.