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

Abstract

The generalized $k$-connectivity of a graph $G$, denoted by ${\kappa }_k(G)$, is the minimum number of internally edge disjoint $S$-trees for any $S\subseteq 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. The burnt pancake graph $B{P}_n$ and the godan graph $E{A}_n$ are two kinds of Cayley graphs which posses many desirable properties. In this paper, we investigate the generalized 3-connectivity of $B{P}_n$ and $E{A}_n$. We show that ${\kappa }_3(B{P}_n)=n-1$ and ${\kappa }_3(E{A}_n)=n-1$.

arXiv admin note: text overlap with arXiv:2211.00320