The generalized 4-connectivity of burnt pancake graphs.

The generalized k -connectivity of a graph G , denoted by κ k (G) , is the minimum number of internally disjoint S -trees for any S ⊆ V (G) and | S | = k. The generalized k -connectivity is a natural extension of the classical connectivity and plays a key role in applications related to the modern interconnection networks. An n -dimensional burnt pancake graph B P n is a Cayley graph which possesses many desirable properties. In this paper, we try to evaluate the reliability of B P n by investigating its generalized 4-connectivity. By introducing the definition of inclusive tree and by studying structural properties of B P n , we show that κ 4 (B P n) = n − 1 for n ≥ 2 , that is, for any four vertices in B P n , there exist (n − 1) internally disjoint trees connecting them in B P n . [ABSTRACT FROM AUTHOR]