The generalized 3-connectivity of burnt pancake graphs and godan graphs

Abstract

AbstractThe generalized k-connectivity of a graph G, denoted by [Formula: see text] is the minimum number of internally edge disjoint S-trees for any [Formula: see text] and [Formula: see text] 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. The burnt pancake graph BPn and the godan graph EAn are two kinds of Cayley graphs which posses many desirable properties. In this paper, we investigate the generalized 3-connectivity of BPn and EAn. We show that [Formula: see text] where [Formula: see text] and [Formula: see text] where [Formula: see text]

Keywords

• interconnection network
• Cayley graph
• generalized k-connectivity
• tree
• 05C40
• 05C05