2023/10/02 by Wang, Jing, Wu, Jiang, Ouyang, Zhangdong +1 · 1 citation
#05C05 #05C40 #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2310.00878
The generalized k-connectivity of a graph G, denoted by κk(G), is the minimum number of internally edge 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 BPn is a Cayley graph which posses many desirable properties. In this paper, we try to evaluate the reliability of BPn by investigating its generalized 4-connectivity. By introducing the notation of inclusive tree and by studying structural properties of BPn, we show that κ4(BPn)=n-1 for n≥ 2, that is, for any four vertices in BPn, there exist (n-1) internally edge disjoint trees connecting them in BPn.