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 ⊆ 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 κ m ( G ) , is the cardinality of the minimum m -component cut. Let C F n 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 κ 3 ( C F n ) = 3 n − 6 ( n is odd) and c κ 3 ( C F n ) = 3 n − 7 ( n is even) for n ≥ 3 ; c κ 4 ( C F n ) = 9 n − 21 2 ( n is odd) and c κ 4 ( C F n ) = 9 n − 24 2 ( n is even) for n ≥ 4 .