The generalized 4-connectivity of burnt pancake graphs***This work was
supported by National Science Foundation of China(No.12271157 & No.12371346),
Natural Science Foundation of Hunan Province (No.2022JJ30028 &
No.2023JJ30072).

Jing Wang1, Jiang Wu1, Zhangdong Ouyang2, Yuanqiu Huang3
1 School of Mathematics, Changsha University, Changsha, China

2 School of Mathematics, Hunan First Normal University, Changsha, China

3 School of Mathematics, Hunan Normal University, Changsha, China

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. An
$n$-dimensional burnt pancake graph $BP_{n}$ is a Cayley graph which posses
many desirable properties. In this paper, we try to evaluate the reliability
of $BP_{n}$ by investigating its generalized 4-connectivity. By introducing
the definition of inclusive tree and by studying structural properties of
$BP_{n}$, we show that $\kappa_{4}(BP_{n})=n-1$ for $n\geq 2$, that is, for
any four vertices in $BP_{n}$, there exist ($n-1$) internally edge disjoint
trees connecting them in $BP_{n}$.

Keywords interconnection network, burnt pancake graph, generalized
$k$-connectivity, tree
MR(2000) Subject Classification 05C40, 05C05

##  1 Introduction

With rapid development and advances of very large scale integration technology
and wafer-scale integration technology, multiprocessor systems have been
widely designed and used in our daily life. It is well known that the
underlying topology of the multiprocessor systems can be modelled by a
connected graph $G=(V(G),E(G))$, where $V(G)$ is the set of processors and
$E(G)$ is the set of communication links of multiprocessor systems.

Fault tolerance has become increasingly significant nowadays since
multiprocessor systems failure is inevitable. The connectivity is a key
parameter for measuring fault tolerance of the network. A subset $S\subseteq
V(G)$ of a connected graph $G$ is called a vertex-cut if $G\setminus S$ is
disconnected or trivial. The connectivity $\kappa(G)$ of $G$ is defined as the
minimum cardinality over all vertex-cuts of $G$. Note that the larger
$\kappa(G)$ is, the more reliable the network is. A well known theorem of
Whitney [25] provides an equivalent definition of connectivity. For each
2-subset $S=\\{x,y\\}\subseteq V(G)$, let $\kappa(S)$ denote the maximum
number of internally disjoint ($x,y$)-paths in $G$. Then

$\kappa(G)=\min\\{\kappa(S)~{}|~{}S\subseteq V(G)\;{\rm and}\;|S|=2\\}.$

The generalized $k$-connectivity, which was introduced by Chartrand et al.
[2], is a strengthening of connectivity and can be served as an essential
parameter for measuring reliability and fault tolerance of the network. Let
$G=(V(G),E(G))$ be a simple graph, $S$ be a subset of $V(G)$. A tree $T$ in
$G$ is called an $S$-tree, if $S\subseteq V(T)$. The trees
$T_{1},T_{2},\cdots,T_{r}$ are called internally edge disjoint $S$-trees if
$V(T_{i})\cap V(T_{j})=S$ and $E(T_{i})\cap E(T_{j})=\emptyset$ for any
integers $1\leq i\neq j\leq r$. Let $\kappa_{G}(S)$ denote the maximum number
of internally edge disjoint $S$-trees. For an integer $k$ with $2\leq
k\leq|V(G)|$, the generalized $k$-connectivity of $G$, denoted by
$\kappa_{k}(G)$, is defined as

$\kappa_{k}(G)=\min\\{\kappa_{G}(S)~{}|~{}S\subseteq V(G)\;{\rm
and}\;|S|=k\\}.$

The generalized 2-connectivity is exactly the classical connectivity. Over the
past few years, research on the generalized connectivity has received
meaningful progress. Li et al. [10] derived that it is NP-complete for a
general graph $G$ to decide whether there are $l$ internally disjoint trees
connecting $S$, where $l$ is a fixed integer and $S\subseteq V(G)$. Authors in
[12, 14] investigated the upper and lower bounds of the generalized
connectivity of a general graph $G$.

Many authors tried to study exact values of the generalized connectivity of
graphs. The generalized $k$-connectivity of the complete graph,
$\kappa_{k}(K_{n})$, was determined in [3] for every pair $k,n$ of integers
with $2\leq k\leq n$. The generalized $k$-connectivity of the complete
bipartite graph $K_{a,b}$ was obtained in [11] for all $2\leq k\leq a+b$. For
$k=3$ or $k=4$, the generalized $k$-connectivity of other important classes of
graphs, such as, Cartesian product graphs [13, 16], hypercubes [13, 19], dual
cubes [30], exchanged hypercubes [28], balanced hypercubes [24], locally
twisted cubes [4, 21], hierarchical cubic networks [34], folded hypercubes
[22], divide-and-swap cubes [26], star graphs and bubble-sort graphs [18],
bubble-sort star graphs [31], ($n,k$)-star graphs [15, 32], pancake graphs
[27], several Cayley graphs [17, 29, 33] et al. have draw many scholars’
attention. As we can see, the results on the generalized $k$-connectivity of
networks are almost about $k\leq 4$.

Gates (the founder of Microsoft) and Papadimitriou [7] introduced the Burnt
Pancake Problem in 1979. With deep understanding, it is known that the Burnt
Pancake Problem relates to the construction of networks of parallel
processors. Many scholars worked a lot on structural properties of burnt
pancake graph $BP_{n}$. In [5], Chin et al. proved $BP_{n}$ to be regular and
vertex-transitive. Moreover, the spanning connectivity of $BP_{n}$ was also
determined in [5]. Lai and Yu [8] proved that $BP_{n}$ contains $n$
independent Hamiltonian cycles. In [20], Song et al. found that $BP_{n}$ is a
Cayley graph, in addition, they investigated the super and extra connectivity
of $BP_{n}$. In this paper, we try to evaluate the reliability of $BP_{n}$ by
studying its generalized 4-connectivity and obtain the following result.

###### Theorem 1.1

For $n\geq 2$, $\kappa_{4}(BP_{n})=n-1$.

This paper is organized as follows. Section 2 introduces some necessary
preliminaries. Section 3 presents the definition and structural properties of
burnt pancake graph $BP_{n}$. Let $S$ be any 4-subset of $V(BP_{n})$. In order
to prove Theorem 1.1, we shall make a lot of efforts in Sections 4, 5 and 6 to
prove that there are ($n-1$)-internally edge disjoint $S$-trees in $BP_{n}$,
depending on the maximum cardinality of $S\cap V(G^{i})$ for $i\in[[n]]$. Then
Theorem 1.1 could be proved in Section 7. Finally, the paper is concluded in
Section 8.

##  2 Preliminary

First of all, we introduce some necessary preliminaries. Let $G=(V(G),E(G))$
be a simple and connected graph with $V(G)$ be its vertex set and $E(G)$ be
its edge set. For a vertex $x\in V(G)$, the degree of $x$ in $G$, denoted by
${\rm deg}_{G}(x)$, is the number of edges of $G$ incident with $x$. Denote
$\delta(G)$ the minimum degree of vertices of $G$. A graph is $r$-regular if
${\rm deg}_{G}(x)=r$ for every vertex $x\in V(G)$. For a vertex $x\in V(G)$,
we use $N_{G}(x)$ to denote the neighbour set of $x$ and $N_{G}[x]$ to denote
$N_{G}(x)\cup\\{x\\}$. Let $V^{\prime}\subseteq V(G)$, denote $G\backslash
V^{\prime}$ be the graph obtained from $G$ by deleting all the vertices in
$V^{\prime}$ together with their incident edges. Denote by $G[V^{\prime}]$ the
subgraph of $G$ induced on $V^{\prime}$.

Let $P$ be a path in $G$ with $x$ and $y$ be its two terminal vertices, then
$P$ is called an $(x,y)$-path. Two ($x,y$)-paths $P_{1}$ and $P_{2}$ are
internally disjoint if they have no common internal vertices, that is,
$V(P_{1})\cap V(P_{2})=\\{x,y\\}$.

The following Lemma 2.1, Lemma 2.2 and Lemma 2.3 are results on the
connectivity of a graph that are well-known in the literature.

###### Lemma 2.1

([1]) Let $G$ be a $k$-connected graph, and let $x$ and $y$ be a pair of
distinct vertices of $G$. Then there exist $k$ internally disjoint
($x,y$)-paths in $G$.

###### Lemma 2.2

([1]) Let $G$ be a $k$-connected graph, let $x$ be a vertex of $G$ and let
$Y\subseteq V(G)\backslash\\{x\\}$ be a set of at least $k$ vertices of $G$.
Then there exists a $k$-fan in $G$ from $x$ to $Y$, that is, there exists a
family of $k$ internally disjoint ($x,Y$)-paths whose terminal vertices are
distinct in $Y$.

###### Lemma 2.3

([1]) Let $G$ be a $k$-connected graph, and let $X$ and $Y$ be subsets of
$V(G)$ of cardinality at least $k$. Then there exists a family of $k$ pairwise
disjoint ($X,Y$)-paths in $G$.

For $3\leq k\leq|V(G)|$, Li gave an upper bound of $\kappa_{k}(G)$ for a
general graph $G$ in her Ph.D. thesis [9].

###### Lemma 2.4

([9]) Let $G$ be a connected graph with minimum degree $\delta(G)$. If there
are two adjacent vertices of degree $\delta(G)$, then
$\kappa_{k}(G)\leq\delta(G)-1$ for $3\leq k\leq|V(G)|$.

The following result is about the relationship between $\kappa_{k}(G)$ and
$\kappa_{k-1}(G)$ of a regular graph $G$.

###### Lemma 2.5

([19]) Let $G$ be an $r$-regular graph. If $\kappa_{k}(G)=r-1$, then
$\kappa_{k-1}(G)=r-1$, where $k\geq 4$.

##  3 The burnt pancake graph $BP_{n}$

Let $[n]=\\{1,2,\cdots,n\\}$. For an integer $i$, it is well known that $|i|$
denotes the absolute value of $i$. Denote $\overline{i}=-i$ in this paper. Let
$[[n]]$ be the set $[n]\cup\\{\overline{i}~{}|~{}i\in[n]\\}$. A signed
permutation of $[n]$ is an $n$-permutation $x_{1}x_{2}\cdots x_{n}$ of $[[n]]$
such that $|x_{1}||x_{2}|\cdots|x_{n}|$ forms a permutation of $[n]$. For a
signed permutation $x=x_{1}x_{2}\cdots x_{n}$ of $[[n]]$ and an integer $i$
($1\leq i\leq n$), the $i$th signed prefix reversal of $x$ is denoted by
$x(i)=\overline{x}_{i}\overline{x_{i-1}}\cdots\overline{x_{1}}x_{i+1}\cdots
x_{n}$.

Figure 1: The burnt pancake graph $BP_{2}$

Figure 2: The burnt pancake graph $BP_{3}$

###### Definition 3.1

([5]) For $n\geq 2$, an $n$-dimensional burnt pancake graph $BP_{n}$ is a
graph with vertex set $V(BP_{n})=\\{x\,|x$ is a signed permutation of
$[[n]]\\}$. Two vertices $x=x_{1}x_{2}\cdots x_{n}$ and $y=y_{1}y_{2}\cdots
y_{n}$ are adjacent in $BP_{n}$ if and only if there exists an integer $i$
($1\leq i\leq n$) such that $x(i)=y$.

The burnt pancake graphs $BP_{2}$ and $BP_{3}$ are depicted in Figure 2 and
Figure 2, respectively. Note that, by fixing the symbol $i$ in the rightmost
position of each vertex for $i\in[[n]]$, $BP_{n}$ can be decomposed into $2n$
vertex disjoint subgraphs $BP_{n}^{i}$, called clusters. Obviously,
$BP_{n}^{i}$ is isomorphic to $BP_{n-1}$ for each $i\in[[n]]$. We write the
construction of $BP_{n}$ symbolically as

$BP_{n}=BP_{n}^{1}\oplus BP_{n}^{\overline{1}}\oplus BP_{n}^{2}\oplus
BP_{n}^{\overline{2}}\oplus\cdots\oplus BP_{n}^{n}\oplus
BP_{n}^{\overline{n}}.$

For simplicity, we shall use $G^{i}$ to replace $BP_{n}^{i}$ in the following
texts for $i\in[[n]]$. That means

$BP_{n}=G^{1}\oplus G^{\overline{1}}\oplus G^{2}\oplus
G^{\overline{2}}\oplus\cdots\oplus G^{n}\oplus G^{\overline{n}}.$

Let $x=x_{1}x_{2}\cdots x_{n}$ be a vertex in $V(G^{x_{n}})$, it is seen that
$x(n)$, the $n$th-signed prefix reversal of $x$, belong to a different cluster
$G^{\overline{x_{1}}}$. We say that $xx(n)$ is a cross edge between
$G^{x_{n}}$ and $G^{\overline{x_{1}}}$. Moreover, we say that $x(n)$ is the
out-neighbour of $x$ and denote it by $\widehat{x}$. The following Lemma 3.1
presents some properties of $BP_{n}$.

###### Lemma 3.1

([6, 7, 20, 23]) For $n\geq 2$, the burnt pancake graph $BP_{n}$ has the
following properties:
(1) It is an $n$-regular Cayley graph with $2^{n}n!$ vertices and $n\times
n!\times 2^{n-1}$ edges;
(2) $\kappa(BP_{n})=n$ and $\kappa_{3}(BP_{n})=n-1$;
(3) The girth of $BP_{n}$ is 8;
(4) For $i\in[[n]]$, no two vertices in $V(G^{i})$ have a common out-
neighbour. Furthermore, let $x=x_{1}x_{2}\cdots x_{n}$ be a vertex in
$V(G^{x_{n}})$, the out-neighbours of vertices in $N_{G^{x_{n}}}[x]$ belong to
$n$ different clusters of $BP_{n}$;
(5) For $\\{i,j\\}\subseteq[[n]]$, we denote by $E(G^{i},G^{j})$ the set of
cross edges between $G^{i}$ and $G^{j}$. Then

$|E(G^{i},G^{j})|=\left\\{\begin{array}[]{ll}0,&\;{\rm if}\;i=\overline{j};\\\
\\\ (n-2)!\times 2^{n-2},&\;{\rm if}\;i\neq\overline{j}.\end{array}\right.$

The following result is not difficult to obtain. Since it appears several
times in the paper, we state it formally.

###### Lemma 3.2

Let $n\geq 3$ and $BP_{n}=G^{1}\oplus G^{\overline{1}}\oplus G^{2}\oplus
G^{\overline{2}}\oplus\cdots\oplus G^{n}\oplus G^{\overline{n}}$. If $x$ is a
vertex in $V(G^{i})$ with $\widehat{x}\in V(G^{j})$, where $i\in[[n]]$ and
$j\in[[n]]\backslash\\{i,\overline{i}\\}$. Then $\widehat{x}(1)\in
V(G^{\overline{j}})$.

###### Lemma 3.3

Let $n\geq 3$ and $BP_{n}=G^{1}\oplus G^{\overline{1}}\oplus G^{2}\oplus
G^{\overline{2}}\oplus\cdots\oplus G^{n}\oplus G^{\overline{n}}$. If $x$ is a
vertex in $V(G^{j})$, where $j\in[[n]]$. Then $G^{j}\backslash\\{x,x(i)\\}$ is
connected, $1\leq i\leq n-1$.

Proof For $n\geq 4$, $G^{j}\backslash\\{x,x(i)\\}$ is connected since
$\kappa(G^{j})=\kappa(BP_{n-1})=n-1>2$ according to Lemma 3.1(2). For $n=3$,
note that $G^{j}$ is isomorphic to a cycle of length 8, moreover, $x$ and
$x(i)$ are adjacent to each other in $G^{j}$. Hence,
$G^{j}\backslash\\{x,x(i)\\}$ is connected for $1\leq i\leq n-1$. $\Box$

Let $n\geq 2$ and $x=x_{1}x_{2}\cdots x_{n}$ be a vertex in $V(G^{x_{n}})$.
For $i\in[n]\backslash\\{x_{n},\overline{x}_{n}\\}$, there is a vertex in
$N_{G^{x_{n}}}(x)$ whose out-neighbour either belong to $V(G^{i})$ or belong
to $V(G^{\overline{i}})$. For $i\in[n]\backslash\\{x_{n},\overline{x}_{n}\\}$,
denote by $\Gamma_{i}(x)$ the vertex in $N_{G^{x_{n}}}(x)$ that its out-
neighbour $\widehat{\Gamma}_{i}(x)\in V(G^{i})\cup V(G^{\overline{i}}).$
Throughout this paper, we use $P(x,\widehat{\Gamma}_{i}(x))$ to denote the
path $\\{x\Gamma_{i}(x),\Gamma_{i}(x)\widehat{\Gamma}_{i}(x)\\}$. That means

$P(x,\widehat{\Gamma}_{i}(x))=\\{x\Gamma_{i}(x),\Gamma_{i}(x)\widehat{\Gamma}_{i}(x)\\}.$

Let $BP_{n}=G^{1}\oplus G^{\overline{1}}\oplus G^{2}\oplus
G^{\overline{2}}\oplus\cdots\oplus G^{n}\oplus G^{\overline{n}}$ and
$S=\\{x,y,z,w\\}$ be any 4-subset of $V(BP_{n})$ for $n\geq 3$. Our following
discussions in Section 4, Section 5 and Section 6 are based on the maximum
value of $|S\cap V(G^{i})|$ for $i\in[[n]]$.

##  4  $\max\\{|S\cap V(G^{i})|\\}=3$ for $i\in[[n]]$

For convenience, hereafter we will use IDSTs and IDPs to represent internally
edge disjoint $S$-trees and internally disjoint paths, respectively.

###### Lemma 4.1

For $n\geq 3$, let $BP_{n}=G^{1}\oplus G^{\overline{1}}\oplus G^{2}\oplus
G^{\overline{2}}\oplus\cdots\oplus G^{n}\oplus G^{\overline{n}}$ and
$S=\\{x,y,z,w\\}$ be any 4-subset of $V(BP_{n})$. If there is an integer
$i\in[[n]]$ such that $|S\cap V(G^{i})|=3$. Then there exist ($n-1$) IDSTs in
$BP_{n}$.

Proof Without loss of generality, we may assume that $\\{x,y,z\\}\subseteq
V(G^{n})$ and $w\in V(G^{j})$, where $j\in[[n]]\backslash\\{n\\}$.
Furthermore, we may assume that $x=12\cdots n$. Note that $\Gamma_{i}(x)=x(i)$
and $\widehat{\Gamma}_{i}(x)\in V(G^{i})$ for $i\in[n-1]$.

Let

$I_{1}=\\{i\in[n-1]~{}|~{}\\{\widehat{\Gamma}_{i}(x),\widehat{\Gamma}_{i}(z)\\}\subseteq
V(G^{i})~{}{\rm and}~{}\widehat{\Gamma}_{i}(y)\in V(G^{\overline{i}})\\},$ (1)
$I_{2}=\\{i\in[n-1]~{}|~{}\widehat{\Gamma}_{i}(x)\in V(G^{i})~{}{\rm
and}~{}\\{\widehat{\Gamma}_{i}(y),\widehat{\Gamma}_{i}(z)\\}\subseteq
V(G^{\overline{i}})\\},$ (2)
$I_{3}=\\{i\in[n-1]~{}|~{}\\{\widehat{\Gamma}_{i}(x),\widehat{\Gamma}_{i}(y)\\}\subseteq
V(G^{i})~{}{\rm and}~{}\widehat{\Gamma}_{i}(z)\in V(G^{\overline{i}})\\},$ (3)
$I_{4}=\\{i\in[n-1]~{}|~{}\\{\widehat{\Gamma}_{i}(x),\widehat{\Gamma}_{i}(y),\widehat{\Gamma}_{i}(z)\\}\subseteq
V(G^{i})\\}.$ (4)

By Lemma 3.1(3), the subgraph $G^{n}[\\{x,y,z\\}]$ contains at most two edges.

Case 1. The subgraph $G^{n}[\\{x,y,z\\}]$ is empty.

For simplicity, we may assume that $I_{1}=\\{1,\cdots,l_{1}\\}$,
$I_{2}=\\{l_{1}+1,\cdots,l_{2}\\}$, $I_{3}=\\{l_{2}+1,\cdots,l_{3}\\}$ and
$I_{4}=\\{l_{3}+1,\cdots,n-1\\}$. It is possible that $I_{i}=\emptyset$ for
$i\in[4]$. The possibility that $I_{i}=\emptyset$ for $i\in[3]$ will not
affect the following discussions.

Subcase 1.1. $j=\overline{n}$.

That means $w\in V(G^{\overline{n}})$. By Lemma 3.1(5), there are ($n-1$)
vertices $w_{1},\cdots,w_{n-1}$ in $V(G^{\overline{n}})$ that
$\widehat{w}_{i}\in V(G^{i})$ for $i\in[n-1]$. According to Lemma 2.2 and the
fact that $\kappa(G^{\overline{n}})=\kappa(BP_{n-1})=n-1$, there is an
($n-1$)-fan $P_{1},\cdots,P_{n-1}$ in $G^{\overline{n}}$ from $w$ to
$\\{w_{1},\cdots,w_{n-1}\\}$ that $w_{i}\in V(P_{i})$ for $i\in[n-1]$.

Subcase 1.1.1. $I_{4}\neq\emptyset$.

That means $(n-1)\in I_{4}$. For $i\in I_{4}$, there is a
$\\{\widehat{\Gamma}_{i}(x),\widehat{\Gamma}_{i}(y),\widehat{\Gamma}_{i}(z),\widehat{w}_{i}\\}$-tree
$\widehat{T}_{i}$ in $G^{i}$ since $G^{i}$ is connected. For $i\in I_{4}$, let

$\displaystyle T_{i}=\widehat{T}_{i}\cup P(x,\widehat{\Gamma}_{i}(x))\cup
P(y,\widehat{\Gamma}_{i}(y))\cup P(z,\widehat{\Gamma}_{i}(z))\cup
P_{i}\cup\\{w_{i}\widehat{w}_{i}\\}.$ (5)

By Lemma 3.1(5) and Lemma 3.2, for $1\leq i\leq l_{3}$, there are vertices
$a_{i}$ and $b_{i}=a_{i}(1)$ in $V(G^{\overline{n-1}})$ such that
$\widehat{a}_{i}\in V(G^{i})$ and $\widehat{b}_{i}\in V(G^{\overline{i}})$.

Figure 3: Illustration for Subcase 1.1.1

For $i\in I_{2}$, there is a
$\\{\widehat{\Gamma}_{i}(x),\widehat{w}_{i},\widehat{a}_{i}\\}$-tree
$T^{\prime}_{i}$ in $G^{i}$ since $G^{i}$ is connected. Moreover, there is a
$\\{\widehat{b}_{i},\widehat{\Gamma}_{i}(y),\widehat{\Gamma}_{i}(z)\\}$-tree
$T^{\prime\prime}_{i}$ in $G^{\overline{i}}$. Let

$IT_{i}=T^{\prime}_{i}\cup
T^{\prime\prime}_{i}\cup\\{a_{i}\widehat{a}_{i},a_{i}b_{i},b_{i}\widehat{b}_{i}\\},\;\;i\in
I_{2}.$

For $i\in I_{2}$, we say that $IT_{i}$ is a
$\\{\widehat{\Gamma}_{i}(x),\widehat{\Gamma}_{i}(y),\widehat{\Gamma}_{i}(z),\widehat{w}_{i}\\}$-inclusive
tree connects $G^{i}$ and $G^{\overline{i}}$ passing through $a_{i}b_{i}$.
Similarly, there exists a
$\\{\widehat{\Gamma}_{i}(x),\widehat{\Gamma}_{i}(y),\widehat{\Gamma}_{i}(z),\widehat{w}_{i}\\}$-inclusive
tree $IT_{i}$ connects $G^{i}$ and $G^{\overline{i}}$ passing through
$a_{i}b_{i}$ for all $i\in I_{1}\cup I_{3}$.

For $1\leq i\leq l_{3}$, let

$\displaystyle T_{i}=IT_{i}\cup P(x,\widehat{\Gamma}_{i}(x))\cup
P(y,\widehat{\Gamma}_{i}(y))\cup P(z,\widehat{\Gamma}_{i}(z))\cup
P_{i}\cup\\{w_{i}\widehat{w}_{i}\\}.$ (6)

See Figure 3. Then $T_{1},\cdots,T_{n-1}$ are ($n-1$) IDSTs in $BP_{n}$.

Subcase 1.1.2. $I_{4}=\emptyset$.

Subcase 1.1.2.1. $\min\\{|I_{1}|,|I_{2}|,|I_{3}|\\}\geq 2$.

By Lemma 3.1(5), there is a
$\\{\widehat{\Gamma}_{i}(x),\widehat{\Gamma}_{i}(z),\widehat{w}_{i},\widehat{\Gamma}_{i+1}(y)\\}$-tree
$\widehat{T}_{i}$ in $G^{i}\cup G^{\overline{i+1}}$ for $1\leq i\leq l_{1}-1$.
Meanwhile, there is a
$\\{\widehat{\Gamma}_{l_{1}}(x),\widehat{w}_{l_{1}},\widehat{\Gamma}_{l_{1}}(z),\widehat{\Gamma}_{1}(y)\\}$-tree
$\widehat{T}_{l_{1}}$ in $G^{l_{1}}\cup G^{\overline{1}}$.

For $1\leq i\leq{l_{1}}$, let

$T_{i}=\widehat{T}_{i}\cup P(x,\widehat{\Gamma}_{i}(x))\cup
P(y,\widehat{\Gamma}_{i+1}(y))\cup P(z,\widehat{\Gamma}_{i}(z))\cup
P_{i}\cup\\{w_{i}\widehat{w}_{i}\\}.$

The subscripts are read modulo $l_{1}$. We may construct other IDSTs
$T_{l_{1}+1},\cdots,T_{n-1}$ by similar analysis. Therefore, $T_{1},$
$\cdots,T_{n-1}$ are ($n-1$) IDSTs in $BP_{n}$.

Subcase 1.1.2.2. $|I_{i}|\leq 1$ for $1\leq i\leq 3$.

To avoid duplication, we consider the case that $|I_{1}|=1$, i.e.,
$I_{1}=\\{1\\}$.

Under this situation, it is impossible that $I_{2}=I_{3}=\emptyset$ since
$n\geq 3$. Without loss of generality, we may assume that
$I_{2}\neq\emptyset$. That means $2\in I_{2}$. By Lemma 3.1(5) and Lemma 3.2,
there exists a vertex $u$ in
$V(G^{2})\backslash\\{\widehat{\Gamma}_{2}(x),\widehat{w}_{2}\\}$ such that
$\widehat{u}\in V(G^{1})$ and $\widehat{u}(1)\in V(G^{\overline{1}})$.

The following two subcases are distinguished to construct $T_{i}$s for $i\in
I_{1}\cup I_{2}$.

Subcase 1.1.2.2.1. $|I_{2}|=1$.

There exists a vertex $v\in
V(G^{\overline{1}})\backslash\\{\widehat{\Gamma}_{1}(y),\widehat{u}(1)\\}$
such that $\widehat{v}\in V(G^{2})$ and $\widehat{v}(1)\in
V(G^{\overline{2}})$. This could be done since $(n-2)!\times 2^{n-2}\geq 2$
when $n\geq 3$. By Lemma 3.3, both $G^{2}\backslash\\{u,u(1)\\}$ and
$G^{\overline{1}}\backslash\\{v,v(1)\\}$ are connected. By similar analysis in
Subcase 1.1.1, there is a
$\\{\widehat{\Gamma}_{1}(x),\widehat{\Gamma}_{1}(y),\widehat{\Gamma}_{1}(z),\widehat{w}_{1}\\}$-inclusive
tree $IT_{1}$ connects $G^{1}$ and $G^{\overline{1}}\backslash\\{v,v(1)\\}$
passing through $uu(1)$ and a
$\\{\widehat{\Gamma}_{2}(x),\widehat{\Gamma}_{2}(y),\widehat{\Gamma}_{2}(z),\widehat{w}_{2}\\}$-inclusive
tree $IT_{2}$ connects $G^{2}\backslash\\{u,u(1)\\}$ and $G^{\overline{2}}$
passing through $vv(1)$, respectively. For $i\in I_{1}\cup I_{2}$, let $T_{i}$
be the same as in Eq.(6).

Subcase 1.1.2.2.2. $|I_{2}|\geq 2$.

By similar arguments in Subcase 1.1.1, there is a
$\\{\widehat{\Gamma}_{1}(x),\widehat{\Gamma}_{1}(y),\widehat{\Gamma}_{1}(z),\widehat{w}_{1}\\}$-inclusive
tree $IT_{1}$ connects $G^{1}$ and $G^{\overline{1}}$ passing through $uu(1)$.
For $i=1$, let $T_{i}$ be the same as in Eq.(6).

According to Lemma 3.3 and Lemma 3.1,
$\big{(}G^{2}\backslash\\{u,u(1)\\}\big{)}\cup G^{\overline{3}}$ is connected.
Thus, there is a
$\\{\widehat{\Gamma}_{2}(x),\widehat{w}_{2},\widehat{\Gamma}_{3}(y),\widehat{\Gamma}_{3}(z)\\}$-tree
$\widehat{T}_{2}$ in $\big{(}G^{2}\backslash\\{u,u(1)\\}\big{)}\cup
G^{\overline{3}}$. For $i\in I_{2}$, let $T_{i}$ be the same as in Subcase
1.1.2.1.

For $i\in I_{3}$, we may let $T_{i}$ be the same as in Subcase 1.1.2.1 if
$|I_{3}|\geq 2$ and construct $T_{i}$ by similar methods in Subcase 1.1.2.2.1
if $|I_{3}|=1$.

Then $T_{1},\cdots,T_{n-1}$ are ($n-1$) IDSTs in $BP_{n}$.

Subcase 1.2. $\overline{j}\in I_{4}$.

Without loss of generality, we may assume that $j=\overline{n-1}$. That is to
say, $w\in V(G^{\overline{n-1}})$. Remind that
$\\{\widehat{\Gamma}_{i}(x),\widehat{\Gamma}_{i}(y),\widehat{\Gamma}_{i}(z)\\}\subseteq
V(G^{i})$ for $i\in I_{4}$. Moreover, either $\widehat{\Gamma}_{i}(w)\in
V(G^{i})$ or $\widehat{\Gamma}_{i}(w)\in V(G^{\overline{i}})$ for $1\leq i\leq
n-2$.

By Lemma 3.2, there are $2(n-1)$ vertices $a_{i}$ and $b_{i}=a_{i}(1)$ in
$V(G^{\overline{n}})$ satisfying $\widehat{a}_{i}\in V(G^{i})$ and
$\widehat{b}_{i}\in V(G^{\overline{i}})$ for $i\in[n-1]$. According to similar
analysis in Subcase 1.1.1, there exists a
$\\{\widehat{\Gamma}_{i}(x),\widehat{\Gamma}_{i}(y),\widehat{\Gamma}_{i}(z),\widehat{\Gamma}_{i}(w)\\}$-inclusive
tree $IT_{i}$ connects $G^{i}$ and $G^{\overline{i}}$ passing through
$a_{i}b_{i}$ for $i\in[n-2]$.

Let $W=\\{\Gamma_{1}(w),\cdots,\Gamma_{n-2}(w)\\}.$ Note that
$|W|=n-2<\kappa(G^{\overline{n-1}})$, $G^{\overline{n-1}}\backslash W$ is
connected. There is a ($w,\widehat{b}_{n-1}$)-path $R_{n-1}$ in
$G^{\overline{n-1}}\backslash W$. Furthermore, there is a
$\\{\widehat{\Gamma}_{n-1}(x),\widehat{\Gamma}_{n-1}(y),\widehat{\Gamma}_{n-1}(z),$
$\widehat{a}_{n-1}\\}$-tree $\widehat{T}_{n-1}$ in $G^{n-1}$. Let

$\displaystyle T_{n-1}$ $\displaystyle=$ $\displaystyle\widehat{T}_{n-1}\cup
R_{n-1}\cup\\{a_{n-1}\widehat{a}_{n-1},a_{n-1}b_{n-1},b_{n-1}\widehat{b}_{n-1}\\}$
$\displaystyle\cup P(x,\widehat{\Gamma}_{n-1}(x))\cup
P(y,\widehat{\Gamma}_{n-1}(y))\cup P(z,\widehat{\Gamma}_{n-1}(z)).$

For $1\leq i\leq n-2$, let

$\displaystyle T_{i}=IT_{i}\cup P(x,\widehat{\Gamma}_{i}(x))\cup
P(y,\widehat{\Gamma}_{i}(y))\cup P(z,\widehat{\Gamma}_{i}(z))\cup
P(w,\widehat{\Gamma}_{i}(w)).$ (7)

Then $T_{1},\cdots,T_{n-1}$ are ($n-1$) IDSTs in $BP_{n}$.

Subcase 1.3. Either $j\in I_{1}\cup I_{2}\cup I_{3}\cup I_{4}$ or
$\overline{j}\in I_{1}\cup I_{2}\cup I_{3}$.

Without loss of generality, we may assume that $j=n-1$, i.e., $w\in
V(G^{n-1})$. For $i\in[n-2]$, define $a_{i}$ and $b_{i}$ be the same as in
Subcase 1.2. There is a
$\\{\widehat{\Gamma}_{i}(x),\widehat{\Gamma}_{i}(y),\widehat{\Gamma}_{i}(z),\widehat{\Gamma}_{i}(w)\\}$-inclusive
tree $IT_{i}$ connects $G^{i}$ and $G^{\overline{i}}$ passing through
$a_{i}b_{i}$ for $i\in[n-2]$. Furthermore, there is a
$\\{\widehat{\Gamma}_{n-1}(x),\widehat{\Gamma}_{n-1}(y),\widehat{\Gamma}_{n-1}(z),w\\}$-tree
$\widehat{T}_{n-1}$ in
$G^{n-1}\backslash\\{\Gamma_{1}(w),\cdots,\Gamma_{n-2}(w)\\}$. Let

$T_{n-1}=\widehat{T}_{n-1}\cup P(x,\widehat{\Gamma}_{n-1}(x))\cup
P(y,\widehat{\Gamma}_{n-1}(y))\cup P(z,\widehat{\Gamma}_{n-1}(z))$

and let $T_{i}$ ($i\in[n-2]$) be the same as in Eq.(7). Then
$T_{1},\cdots,T_{n-1}$ are ($n-1$) IDSTs in $BP_{n}$.

Case 2. The subgraph $G^{n}[\\{x,y,z\\}]$ contains exactly one edge.

Without loss of generality, we may assume that $y=x(l)$, where $1\leq l\leq
n-1$. It yields that $y=\overline{l}\cdots\bar{1}(l+1)\cdots n$. Moreover,
$\widehat{\Gamma}_{i}(y)\in V(G^{\overline{i}})$ for $1\leq i\leq l$ and
$\widehat{\Gamma}_{i}(y)\in V(G^{i})$ for $l+1\leq i\leq n-1$. Note that
$\widehat{\Gamma}_{i}(z)\in V(G^{i})\cup V(G^{\overline{i}})$ for $i\in[n-1]$.

Subcase 2.1. $j=\overline{n}$, i.e., $w\in V(G^{\overline{n}})$.

Subcase 2.1.1. $l\neq 1$.

Consider the locations of $\widehat{\Gamma}_{1}(z)$ and
$\widehat{\Gamma}_{l}(z)$. By former analysis, there are four possibilities:
(1) $\widehat{\Gamma}_{1}(z)\in V(G^{1})$ and $\widehat{\Gamma}_{l}(z)\in
V(G^{l})$; (2) $\widehat{\Gamma}_{1}(z)\in V(G^{1})$ and
$\widehat{\Gamma}_{l}(z)\in V(G^{\overline{l}})$; (3)
$\widehat{\Gamma}_{1}(z)\in V(G^{\overline{1}})$ and
$\widehat{\Gamma}_{l}(z)\in V(G^{l})$; (4) $\widehat{\Gamma}_{1}(z)\in
V(G^{\overline{1}})$ and $\widehat{\Gamma}_{l}(z)\in V(G^{\overline{l}})$. By
symmetry, we only need to consider the following two cases.

Subcase 2.1.1.1. $\widehat{\Gamma}_{1}(z)\in V(G^{1})$ and
$\widehat{\Gamma}_{l}(z)\in V(G^{l})$.

By Lemma 3.1(5), there are ($n-1$) vertices $w_{1},\cdots,w_{n-1}$ in
$V(G^{\overline{n}})$ such that $\widehat{w}_{i}\in V(G^{i})$ for $i\in[n-1]$.
According to Lemma 2.2, there is a family of ($n-1$) IDPs
$P_{1},\cdots,P_{n-1}$ in $G^{\overline{n}}$ from $w$ to
$\\{w_{1},\cdots,w_{n-1}\\}$ such that $w_{i}\in V(P_{i})$ for $i\in[n-1]$.

Since $G^{1}\cup G^{\overline{l}}$ is connected, there is a
$\\{\widehat{\Gamma}_{1}(x),\widehat{\Gamma}_{1}(z),\widehat{w}_{1},\widehat{\Gamma}_{l}(y)\\}$-tree
$\widehat{T}_{1}$ in $G^{1}\cup G^{\overline{l}}$. Furthermore, there is a
$\\{\widehat{y},\widehat{\Gamma}_{l}(z),\widehat{w}_{l}\\}$-tree
$\widehat{T}_{l}$ in $G^{l}$. Let

$\displaystyle T_{1}=\widehat{T}_{1}\cup P(x,\widehat{\Gamma}_{1}(x))\cup
P(z,\widehat{\Gamma}_{1}(z))\cup P(y,\widehat{\Gamma}_{l}(y))\cup
P_{1}\cup\\{w_{1}\widehat{w}_{1}\\}$

and

$\displaystyle T_{l}=\widehat{T}_{l}\cup P(z,\widehat{\Gamma}_{l}(z))\cup
P_{l}\cup\\{xy,y\widehat{y},w_{l}\widehat{w}_{l}\\}.$

By Lemma 3.2, for $i\in[n-1]\backslash\\{1,l\\}$, there are 2($n-3$) vertices
$a_{i}$ and $b_{i}=a_{i}(1)$ in $V(G^{\overline{1}})$ such that
$\widehat{a}_{i}\in V(G^{i})$ and $\widehat{b}_{i}\in V(G^{\overline{i}})$. By
similar analysis in Subcase 1.1.1, we can find a
$\\{\widehat{\Gamma}_{i}(x),\widehat{\Gamma}_{i}(y),\widehat{\Gamma}_{i}(z),\widehat{w}_{i}\\}$-inclusive
tree $IT_{i}$ connects $G^{i}$ and $G^{\overline{i}}$ passing through
$a_{i}b_{i}$ and construct $T_{i}$ be the same as in Eq.(6), for
$i\in[n-1]\backslash\\{1,l\\}$. See Figure 5. Then $T_{1},\cdots,T_{n-1}$ are
($n-1$) IDSTs in $BP_{n}$.

Figure 4: Illustration for Subcase 2.1.1.1

Figure 5: Illustration for Subcase 2.1.1.2

Subcase 2.1.1.2. $\widehat{\Gamma}_{1}(z)\in V(G^{1})$ and
$\widehat{\Gamma}_{l}(z)\in V(G^{\overline{l}})$.

By Lemma 3.1(5), there are ($n-1$) vertices $w_{1},\cdots,w_{n-1}$ in
$V(G^{\overline{n}})$ such that $\widehat{w}_{l}\in V(G^{\overline{l}})$ and
$\widehat{w}_{i}\in V(G^{i})$ for $i\in[n-1]\backslash\\{l\\}$. According to
Lemma 2.2, there is a family of ($n-1$) IDPs $P_{1},\cdots,P_{n-1}$ in
$G^{\overline{n}}$ from $w$ to $\\{w_{1},\cdots,w_{n-1}\\}$ such that
$w_{i}\in V(P_{i})$ for $i\in[n-1]$.

Based on Lemma 3.1, there is a
$\\{\widehat{\Gamma}_{1}(x),\widehat{\Gamma}_{1}(z),\widehat{w}_{1},\widehat{y}\\}$-tree
$\widehat{T}_{1}$ in $G^{1}\cup G^{l}$ and a
$\\{\widehat{\Gamma}_{l}(y),\widehat{\Gamma}_{l}(z),\widehat{w}_{l}\\}$-tree
$\widehat{T}_{l}$ in $G^{\overline{l}}$. Let

$\displaystyle T_{1}=\widehat{T}_{1}\cup P(x,\widehat{\Gamma}_{1}(x))\cup
P(z,\widehat{\Gamma}_{1}(z))\cup
P_{1}\cup\\{y\widehat{y},w_{1}\widehat{w}_{1}\\}$

and

$\displaystyle T_{l}=\widehat{T}_{l}\cup P(y,\widehat{\Gamma}_{l}(y))\cup
P(z,\widehat{\Gamma}_{l}(z))\cup P_{l}\cup\\{xy,w_{l}\widehat{w}_{l}\\}.$

For $i\in[n-1]\backslash\\{1,l\\}$, $IT_{i}$ and $T_{i}$ may be defined by
similar methods in Subcase 2.1.1.1. See Figure 5. Then $T_{1},\cdots,T_{n-1}$
are ($n-1$) IDSTs in $BP_{n}$.

Subcase 2.1.2. $l=1$.

Note that either $\widehat{\Gamma}_{1}(z)\in V(G^{1})$ or
$\widehat{\Gamma}_{1}(z)\in V(G^{\overline{1}})$. By symmetry, we only need to
consider the possibility that $\widehat{\Gamma}_{1}(z)\in V(G^{1})$.

There are ($n-1$) vertices $w_{1},\cdots,w_{n-1}$ in $V(G^{\overline{n}})$
such that $\widehat{w}_{i}\in V(G^{i})$ for $i\in[n-1]$. According to Lemma
2.2, there is a family of ($n-1$) IDPs $P_{1},\cdots,P_{n-1}$ in
$G^{\overline{n}}$ from $w$ to $\\{w_{1},\cdots,w_{n-1}\\}$ such that
$w_{i}\in V(P_{i})$ for $i\in[n-1]$.

Since $G^{1}$ is connected, there exists a
$\\{\widehat{y},\widehat{\Gamma}_{1}(z),\widehat{w}_{1}\\}$-tree
$\widehat{T}_{1}$ in $G^{1}$. Let

$\displaystyle T_{1}=\widehat{T}_{1}\cup P(z,\widehat{\Gamma}_{1}(z))\cup
P_{1}\cup\\{xy,y\widehat{y},w_{1}\widehat{w}_{1}\\}$

and let $T_{i}$ be the same as in Subcase 2.1.1.1 for $2\leq i\leq n-1$. See
Figure 7. Then $T_{1},\cdots,T_{n-1}$ are ($n-1$) IDSTs in $BP_{n}$.

Subcase 2.2. $j\in\\{1,\overline{1},l,\overline{l}\\}$.

To avoid duplication, we only consider the case that $j=1$.

Denote by $v=\widehat{\Gamma}_{l}(y)$ for simplicity. Remind that
$\widehat{\Gamma}_{1}(\widehat{y})\in V(G^{1})\cup V(G^{\overline{1}})$ and
$\widehat{\Gamma}_{1}(v)\in V(G^{1})\cup V(G^{\overline{1}})$. Since each
vertex has an unique out-neighbour, either
$\widehat{\Gamma}_{1}(\widehat{y})\neq\Gamma_{l}(w)$ or
$\widehat{\Gamma}_{1}(v)\neq\Gamma_{l}(w)$. Without loss of generality, we may
assume that $\widehat{\Gamma}_{1}(\widehat{y})\neq\Gamma_{l}(w)$.

Figure 6: Illustration for Subcase 2.1.2

Figure 7: Illustration for Subcase 2.2

There exist 2($n-1$) vertices $a_{i}$ and $b_{i}=a_{i}(1)$ in
$V(G^{\overline{n}})$ such that $\widehat{a}_{i}\in V(G^{i})$ and
$\widehat{b}_{i}\in V(G^{\overline{i}})$ for $i\in[n-1]$ according to Lemma
3.2.

Let $W=\\{\Gamma_{2}(w),\cdots,\Gamma_{n-1}(w)\\}$. Note that
$|W|=n-2<\kappa(G^{1})$. Then $G^{1}\backslash W$ is connected. By similar
arguments in Subcase 1.1.1, there is a
$\\{\widehat{\Gamma}_{1}(x),w,\widehat{\Gamma}_{1}(z),\widehat{\Gamma}_{1}(\widehat{y})\\}$-inclusive
tree $IT_{1}$ connects $\big{(}G^{1}\backslash W\big{)}$ and
$G^{\overline{1}}$ passing through $a_{1}b_{1}$. Let

$\displaystyle T_{1}=IT_{1}\cup P(x,\widehat{\Gamma}_{1}(x))\cup
P(z,\widehat{\Gamma}_{1}(z))\cup\\{y\widehat{y},~{}\widehat{y}\Gamma_{1}(\widehat{y}),~{}\Gamma_{1}(\widehat{y})\widehat{\Gamma}_{1}(\widehat{y})\\}.$

It is seen that $G^{l}\backslash\\{\widehat{y},\Gamma_{1}(\widehat{y})\\}$ is
connected by Lemma 3.3. Using similar analysis in Subcase 1.1.1, there is a
$\\{\widehat{\Gamma}_{l}(y),\widehat{\Gamma}_{l}(z),\widehat{\Gamma}_{l}(w)\\}$-inclusive
tree $IT_{l}$ connects
$\big{(}G^{l}\backslash\\{\widehat{y},\Gamma_{1}(\widehat{y})\\}\big{)}$ and
$G^{\overline{l}}$ passing through $a_{l}b_{l}$. Let

$\displaystyle T_{l}=IT_{l}\cup P(y,\widehat{\Gamma}_{l}(y))\cup
P(z,\widehat{\Gamma}_{l}(z))\cup P(w,\widehat{\Gamma}_{l}(w))\cup\\{xy\\}.$

Again, by similar analysis in Subcase 2.1.1, there is a
$\\{\widehat{\Gamma}_{i}(x),\widehat{\Gamma}_{i}(y),\widehat{\Gamma}_{i}(z),\widehat{\Gamma}_{i}(w)\\}$-inclusive
tree $IT_{i}$ connects $G^{i}$ and $G^{\overline{i}}$ passing through
$a_{i}b_{i}$ for $i\in[n-1]\backslash\\{1,l\\}$. For
$i\in[n-1]\backslash\\{1,l\\}$, let $T_{i}$ be the same as in Eq.(7). See
Figure 7. Then $T_{1},\cdots,T_{n-1}$ are ($n-1$) IDSTs in $BP_{n}$.

Subcase 2.3. Either $j\in[n-1]\backslash\\{1,l\\}$ or
$\overline{j}\in[n-1]\backslash\\{1,l\\}$ .

For simplicity, we may assume that $j=n-1$.

For $i\in[n-1]$, let $a_{i}$ and $b_{i}=a_{i}(1)$ be the same as in Subcase
2.2. In addition, let $W=\\{\Gamma_{1}(w),\cdots,\Gamma_{n-2}(w)\\}$.

Since $G^{n-1}\backslash W$ is connected, there is a
$\\{w,\widehat{\Gamma}_{n-1}(x),\widehat{\Gamma}_{n-1}(y),\widehat{\Gamma}_{n-1}(z)\\}$-inclusive
tree $IT_{n-1}$ connects $\big{(}G^{n-1}\backslash W\big{)}$ and
$G^{\overline{n-1}}$ passing through $a_{n-1}b_{n-1}$. Let

$\displaystyle T_{n-1}=IT_{n-1}\cup P(x,\widehat{\Gamma}_{n-1}(x))\cup
P(y,\widehat{\Gamma}_{n-1}(y))\cup P(z,\widehat{\Gamma}_{n-1}(z)).$

Subcase 2.3.1. $l\neq 1$.

There is a
$\\{\widehat{\Gamma}_{1}(x),\widehat{\Gamma}_{1}(\widehat{y}),\widehat{\Gamma}_{1}(z),\widehat{\Gamma}_{1}(w)\\}$-inclusive
tree $IT_{1}$ connects $G^{1}$ and $G^{\overline{1}}$ passing through
$a_{1}b_{1}$ since
$\\{\widehat{\Gamma}_{1}(\widehat{y}),\widehat{\Gamma}_{1}(w)\\}\subseteq
V(G^{1})\cup V(G^{\overline{1}})$. Furthermore, there is a
$\\{\widehat{\Gamma}_{l}(y),\widehat{\Gamma}_{l}(z),\widehat{\Gamma}_{l}(w)\\}$-inclusive
tree $IT_{l}$ connects
$(G^{l}\backslash\\{\widehat{y},\Gamma_{1}(\widehat{y})\\})$ and
$G^{\overline{l}}$ passing through $a_{l}b_{l}$.

Let

$\displaystyle T_{1}=IT_{1}\cup P(x,\widehat{\Gamma}_{1}(x))\cup
P(z,\widehat{\Gamma}_{1}(z))\cup P(w,\widehat{\Gamma}_{1}(w))\cup
P(\widehat{y},\widehat{\Gamma}_{1}(\widehat{y}))\cup\\{y\widehat{y}\\}.$

For $2\leq i\leq n-2$, we may define $T_{i}$ to be the same as in Subcase 2.2.
Then $T_{1},\cdots,T_{n-1}$ are ($n-1$) IDSTs in $BP_{n}$.

Subcase 2.3.2. $l=1$.

There is a
$\\{\widehat{y},\widehat{\Gamma}_{1}(z),\widehat{\Gamma}_{1}(w)\\}$-inclusive
tree $IT_{1}$ connects $G^{1}$ and $G^{\overline{1}}$ passing through
$a_{1}b_{1}$. Let

$\displaystyle T_{1}=IT_{1}\cup P(z,\widehat{\Gamma}_{1}(z))\cup
P(w,\widehat{\Gamma}_{1}(w))\cup\\{xy,y\widehat{y}\\}.$

For $2\leq i\leq n-2$, we may define $T_{i}$ to be the same as in Subcase 2.2.
Then $T_{1},\cdots,T_{n-1}$ are ($n-1$) IDSTs in $BP_{n}$.

Case 3. The subgraph $G^{n}[\\{x,y,z\\}]$ contains two edges.

Without loss of generality, we may assume that $\\{xy,xz\\}\subseteq
E(G^{n})$. Moreover, let $y=x(l)=\overline{l}\cdots\bar{1}(l+1)\cdots n$ and
$z=x(k)=\overline{k}\cdots\overline{2}\bar{1}(k+1)\cdots n$, where $1\leq
l<k\leq n-1$. It is seen that $\Gamma_{1}(y)=x=\Gamma_{1}(z)$.

Combined above assumptions with Eqs.(1), (2), (3) and (4), we know that
$I_{1}=\emptyset$, $I_{2}=\\{1,\cdots,l\\}$, $I_{3}=\\{l+1,\cdots,k\\}$ and
$I_{4}=\\{k+1,\cdots,n-1\\}$.

Let $I_{2}^{\prime}=I_{2}\backslash\\{1,l\\}$ and
$I_{3}^{\prime}=I_{3}\backslash\\{k\\}$. It is seen that
$I_{2}^{\prime}=\emptyset$ when $l=1$.

Subcase 3.1. $j=\overline{n}$, i.e., $w\in V(G^{\overline{n}})$.

For $i\in[n-1]$, there exists a vertex $w_{i}\in V(G^{\overline{n}})$ whose
out-neighbour $\widehat{w}_{i}\in V(G^{i})$. By Lemma 2.2, there is an
($n-1$)-fan $P_{1},\cdots,P_{n-1}$ in $G^{\overline{n}}$ from $w$ to
$\\{w_{1},\cdots,w_{n-1}\\}$ such that $w_{i}\in V(P_{i})$ for $i\in[n-1]$.

Subcase 3.1.1. $l\neq 1$.

It is seen that there is a
$\\{\widehat{\Gamma}_{1}(x),\widehat{w}_{1},\widehat{\Gamma}_{l}(y),\widehat{\Gamma}_{l}(z)\\}$-tree
$\widehat{T}_{1}$ in $G^{1}\cup G^{\overline{l}}$ according to Lemma 3.1(5).
Analogously, there is a $\\{\widehat{x},\widehat{y},\widehat{w}_{l}\\}$-tree
$\widehat{T}_{l}$ in $G^{\overline{1}}\cup G^{l}$ and a
$\\{\widehat{\Gamma}_{k}(y),\widehat{z},\widehat{w}_{k}\\}$-tree
$\widehat{T}_{k}$ in $G^{k}$, respectively.

Let

$T_{1}=\widehat{T}_{1}\cup P(x,\widehat{\Gamma}_{1}(x))\cup
P(y,\widehat{\Gamma}_{l}(y))\cup P(z,\widehat{\Gamma}_{l}(z))\cup
P_{1}\cup\\{w_{1}\widehat{w}_{1}\\},$ $T_{l}=\widehat{T}_{l}\cup
P_{l}\cup\\{x\widehat{x},xz,y\widehat{y},w_{l}\widehat{w}_{l}\\},$

and

$T_{k}=\widehat{T}_{k}\cup P_{k}\cup
P(y,\widehat{\Gamma}_{k}(y))\cup\\{xy,z\widehat{z},w_{k}\widehat{w}_{k}\\}.$

The trees $T_{1}$, $T_{l}$ and $T_{k}$ are depicted in Figure 9 by blue, red
and green lines, respectively.

There are vertices $a_{i}$ and $b_{i}=a_{i}(1)$ in $V(G^{\overline{k}})$
satisfying $\widehat{a}_{i}\in V(G^{i})$ and $\widehat{b}_{i}\in
V(G^{\overline{i}})$ for each $i\in I_{2}^{\prime}\cup I_{3}^{\prime}$. By
similar arguments in Subcase 1.1.1, there is a
$\\{\widehat{\Gamma}_{i}(x),\widehat{\Gamma}_{i}(y),\widehat{\Gamma}_{i}(z),\widehat{w}_{i}\\}$-inclusive
tree $IT_{i}$ connects $G^{i}$ and $G^{\overline{i}}$ passing through
$a_{i}b_{i}$, $i\in I_{2}^{\prime}\cup I_{3}^{\prime}$. For $i\in I_{4}$,
there is a
$\\{\widehat{\Gamma}_{i}(x),\widehat{\Gamma}_{i}(y),\widehat{\Gamma}_{i}(z),\widehat{w}_{i}\\}$-tree
$\widehat{T}_{i}$ in $G^{i}$ since $G^{i}$ is connected.

Let $T_{i}$ be the same as in Eq.(6) for $i\in I_{2}^{\prime}\cup
I_{3}^{\prime}$ and $T_{i}$ be the same as in Eq.(5) for $i\in I_{4}$. Then
$T_{1},\cdots,T_{n-1}$ are ($n-1$) IDSTs in $BP_{n}$.

Subcase 3.1.2. $l=1$.

Remind that $I_{2}^{\prime}=\emptyset$ under this situation. There are
vertices $a_{i}$ and $b_{i}=a_{i}(1)$ in $V(G^{\overline{k}})$ satisfying
$\widehat{a}_{i}\in V(G^{i})$ and $\widehat{b}_{i}\in V(G^{\overline{i}})$ for
each $1\leq i\leq k-1$. By analogous analysis in Subcase 3.1.1, there is a
$\\{\widehat{x},\widehat{y},\widehat{w}_{1}\\}$-inclusive tree $IT_{1}$
connects $G^{1}$ and $G^{\overline{1}}$ passing through $a_{1}b_{1}$. Set

$T_{1}=IT_{1}\cup
P_{1}\cup\\{x\widehat{x},y\widehat{y},xz,w_{1}\widehat{w}_{1}\\}.$

For $i\in I_{3}\cup I_{4}$, let $T_{i}$ be the same as in Subcase 3.1.1. Then
$T_{1},\cdots,T_{n-1}$ are ($n-1$) IDSTs in $BP_{n}$.

Figure 8: Illustration for Subcase 3.1.1

Figure 9: Illustration for Subcase 3.2.1.1

Subcase 3.2. $j\in\\{1,\overline{1},l,\overline{l}\\}$.

We consider the case that $j=1$, for other cases the proof is similar. Since
$w\in V(G^{1})$, either $\widehat{\Gamma}_{i}(w)\in V(G^{i})$ or
$\widehat{\Gamma}_{i}(w)\in V(G^{\overline{i}})$ for $2\leq i\leq n-1$.

Set $W=\\{\Gamma_{2}(w),\cdots,\Gamma_{n-1}(w)\\}$ and
$\widehat{W}=\\{\widehat{\Gamma}_{2}(w),\cdots,\widehat{\Gamma}_{n-1}(w)\\}.$

Subcase 3.2.1. $l\neq 1$.

Subcase 3.2.1.1. $\widehat{\Gamma}_{l}(w)\in V(G^{l})$.

By analogous analysis in former discussions, $G^{1}\backslash W$ is connected.
Note that $\widehat{W}\cap V(G^{\overline{l}})=\emptyset$. Thus, there is a
$\\{\widehat{\Gamma}_{1}(x),w,\widehat{\Gamma}_{l}(y),\widehat{\Gamma}_{l}(z)\\}$-tree
$\widehat{T}_{1}$ in $\big{(}G^{1}\backslash W\big{)}\cup G^{\overline{l}}$
since $\big{(}G^{1}\backslash W\big{)}\cup G^{\overline{l}}$ is connected by
Lemma 3.1(5). Furthermore, there is a
$\\{\widehat{x},\widehat{y},\widehat{\Gamma}_{l}(w)\\}$-tree $\widehat{T}_{l}$
in $G^{l}\cup G^{\overline{1}}$.

Let

$T_{1}=\widehat{T}_{1}\cup P(x,\widehat{\Gamma}_{1}(x))\cup
P(y,\widehat{\Gamma}_{l}(y))\cup P(z,\widehat{\Gamma}_{l}(z))\\}$

and

$T_{l}=\widehat{T}_{l}\cup
P(w,\widehat{\Gamma}_{l}(w))\cup\\{x\widehat{x},xz,y\widehat{y}\\}.$

For $i\in[n-1]\backslash\\{1,l\\}$, there are vertices $a_{i}$ and
$b_{i}=a_{i}(1)$ in $V(G^{\overline{n}})$ satisfying $\widehat{a}_{i}\in
V(G^{i})$ and $\widehat{b}_{i}\in V(G^{\overline{i}})$. Due to similar
analysis in Subcase 1.1.1, there is a
$\\{\widehat{z},\widehat{\Gamma}_{k}(y),\widehat{\Gamma}_{k}(w)\\}$-inclusive
tree $IT_{k}$ connects $G^{k}$ and $G^{\overline{k}}$ passing through
$a_{k}b_{k}$, furthermore, there is a
$\\{\widehat{\Gamma}_{i}(x),\widehat{\Gamma}_{i}(y),\widehat{\Gamma}_{i}(z),\widehat{\Gamma}_{i}(w)\\}$-inclusive
tree $IT_{i}$ connects $G^{i}$ and $G^{\overline{i}}$ passing through
$a_{i}b_{i}$ for $i\in I_{2}^{\prime}\cup I_{3}^{\prime}\cup I_{4}$.

Let

$T_{k}=IT_{k}\cup P(y,\widehat{\Gamma}_{k}(y))\cup
P(w,\widehat{\Gamma}_{k}(w))\cup\\{xy,z\widehat{z}\\}.$

For $i\in I_{2}^{\prime}\cup I_{3}^{\prime}\cup I_{4}$, let $T_{i}$ be the
same as in Eq.(7). See Figure 9. Then $T_{1},\cdots,T_{n-1}$ are ($n-1$) IDSTs
in $BP_{n}$.

Subcase 3.2.1.2. $\widehat{\Gamma}_{l}(w)\in V(G^{\overline{l}})$.

There is a $\\{\widehat{\Gamma}_{1}(x),w,\widehat{y}\\}$-tree
$\widehat{T}_{1}$ in $\big{(}G^{1}\backslash W\big{)}\cup G^{l}$ and a
$\\{\widehat{x},\widehat{\Gamma}_{l}(y),\widehat{\Gamma}_{l}(z),\widehat{\Gamma}_{l}(w)\\}$-tree
$\widehat{T}_{l}$ in $G^{\overline{1}}\cup G^{\overline{l}}$.

Let

$T_{1}=\widehat{T}_{1}\cup
P(x,\widehat{\Gamma}_{1}(x))\cup\\{y\widehat{y},xz\\}$

and

$T_{l}=\widehat{T}_{l}\cup P(y,\widehat{\Gamma}_{l}(y))\cup
P(z,\widehat{\Gamma}_{l}(z))\cup
P(w,\widehat{\Gamma}_{l}(w))\cup\\{x\widehat{x}\\}.$

See Figure 11. For $i\in[n-1]\backslash\\{1,l\\}$, let $T_{i}$ be the same as
in Subcase 3.2.1.1. Then $T_{1},\cdots,T_{n-1}$ are ($n-1$) IDSTs in $BP_{n}$.

Figure 10: Illustration for Subcase 3.2.1.2

Figure 11: Illustration for Subcase 3.2.2

Subcase 3.2.2. $l=1$.

There are vertices $a_{i}$ and $b_{i}=a_{i}(1)$ in $V(G^{\overline{n}})$
satisfying $\widehat{a}_{i}\in V(G^{i})$ and $\widehat{b}_{i}\in
V(G^{\overline{i}})$ for $i\in[n-1]$. Remind that $G^{1}\backslash W$ is
connected and $\widehat{\Gamma}_{1}(x)=\widehat{y}$, there is a
$\\{\widehat{y},w,\widehat{a}_{1}\\}$-tree $\widehat{T}_{1}$ in
$G^{1}\backslash W$ and a ($\widehat{x},\widehat{b}_{1}$)-path $P_{1}$ in
$G^{\overline{1}}$. In addition, there is a
$\\{\widehat{\Gamma}_{i}(x),\widehat{\Gamma}_{i}(y),\widehat{\Gamma}_{i}(z),\widehat{\Gamma}_{i}(w)\\}$-inclusive
tree $IT_{i}$ connects $G^{i}$ and $G^{\overline{i}}$ passing through
$a_{i}b_{i}$ for $2\leq i\leq n-1$.

Let $T_{1}=\widehat{T}_{1}\cup
P_{1}\cup\\{x\widehat{x},y\widehat{y},xz,a_{1}\widehat{a}_{1},a_{1}b_{1},b_{1}\widehat{b}_{1}\\}$
and let $T_{i}$ be the same as in Subcase 3.2.1.1 for $i\in I_{3}\cup I_{4}$.
See Figure 11. Then $T_{1},\cdots,T_{n-1}$ are ($n-1$) IDSTs in $BP_{n}$.

Subcase 3.3. $j=k$, i.e., $w\in V(G^{k})$.

Let $W=\\{\Gamma_{i}(w)|i\in I_{2}\cup I_{3}^{\prime}\cup I_{4}\\}$.

Clearly, $\\{\widehat{z},\widehat{\Gamma}_{k}(y)\\}\cap W=\emptyset.$ There is
a $\\{\widehat{z},\widehat{\Gamma}_{k}(y),w\\}$-tree $\widehat{T}_{k}$ in
$G^{k}\backslash W$ since $G^{k}\backslash W$ is connected. Let
$T_{k}=\widehat{T}_{k}\cup
P(y,\widehat{\Gamma}_{k}(y))\cup\\{z\widehat{z},xy\\}$.

Subcase 3.3.1. $l\neq 1$.

For $i\in I_{2}^{\prime}\cup I_{3}^{\prime}\cup I_{4}$, there exist vertices
$a_{i}$ and $b_{i}=a_{i}(1)$ in $V(G^{\overline{n}})$ satisfying
$\widehat{a}_{i}\in V(G^{i})$ and $\widehat{b}_{i}\in V(G^{\overline{i}})$.
For $i\in I_{2}^{\prime}\cup I_{3}^{\prime}\cup I_{4}$, we can find a
$\\{\widehat{\Gamma}_{i}(x),\widehat{\Gamma}_{i}(y),\widehat{\Gamma}_{i}(z),\widehat{\Gamma}_{i}(w)\\}$-inclusive
tree $IT_{i}$ connects $G^{i}$ and $G^{\overline{i}}$ passing through
$a_{i}b_{i}$ and let $T_{i}$ be the same as in Eq.(7).

Consider the locations of $\widehat{\Gamma}_{1}(w)$ and
$\widehat{\Gamma}_{l}(w)$. To avoid duplication, we consider the following two
cases.

Subcase 3.3.1.1. $\widehat{\Gamma}_{1}(w)\in V(G^{1})$ and
$\widehat{\Gamma}_{l}(w)\in V(G^{l})$.

There is a
$\\{\widehat{\Gamma}_{1}(x),\widehat{\Gamma}_{1}(w),\widehat{\Gamma}_{l}(y),\widehat{\Gamma}_{l}(z)\\}$-tree
$\widehat{T}_{1}$ in $G^{1}\cup G^{\overline{l}}$ and a
$\\{\widehat{x},\widehat{y},\widehat{\Gamma}_{l}(w)\\}$-tree $\widehat{T}_{l}$
in $G^{l}\cup G^{\overline{1}}$, respectively.

Figure 12: Illustration for Subcase 3.3.1.1

Figure 13: Illustration for Subcase 3.3.1.2

Let

$T_{1}=\widehat{T}_{1}\cup P(x,\widehat{\Gamma}_{1}(x))\cup
P(y,\widehat{\Gamma}_{l}(y))\cup P(z,\widehat{\Gamma}_{l}(z))\cup
P(w,\widehat{\Gamma}_{1}(w))$

and

$T_{l}=\widehat{T}_{l}\cup
P(w,\widehat{\Gamma}_{l}(w))\cup\\{x\widehat{x},y\widehat{y},xz\\}.$

For simplicity, only the trees $T_{1}$, $T_{l}$ and $T_{k}$ are depicted in
Figure 13. Then $T_{1},\cdots,T_{n-1}$ are ($n-1$) IDSTs in $BP_{n}$.

Subcase 3.3.1.2. $\widehat{\Gamma}_{1}(w)\in V(G^{1})$ and
$\widehat{\Gamma}_{l}(w)\in V(G^{\overline{l}})$.

There is a
$\\{\widehat{\Gamma}_{1}(x),\widehat{\Gamma}_{1}(w),\widehat{y}\\}$-tree
$\widehat{T}_{1}$ in $G^{1}\cup G^{l}$ and a
$\\{\widehat{x},\widehat{\Gamma}_{l}(y),\widehat{\Gamma}_{l}(z),\widehat{\Gamma}_{l}(w)\\}$-tree
$\widehat{T}_{l}$ in $G^{\overline{l}}\cup G^{\overline{1}}$, respectively.

Let

$T_{1}=\widehat{T}_{1}\cup P(x,\widehat{\Gamma}_{1}(x))\cup
P(w,\widehat{\Gamma}_{1}(w))\cup\\{y\widehat{y},xz\\}$

and

$T_{l}=\widehat{T}_{l}\cup P(y,\widehat{\Gamma}_{l}(y))\cup
P(z,\widehat{\Gamma}_{l}(z))\cup
P(w,\widehat{\Gamma}_{l}(w))\cup\\{x\widehat{x}\\}.$

See Figure 13. Then $T_{1},\cdots,T_{n-1}$ are ($n-1$) IDSTs in $BP_{n}$.

Subcase 3.3.2. $l=1$.

For $i\in I_{2}\cup I_{3}^{\prime}\cup I_{4}$, there exist vertices $a_{i}$
and $b_{i}=a_{i}(1)$ in $V(G^{\overline{n}})$ satisfying $\widehat{a}_{i}\in
V(G^{i})$ and $\widehat{b}_{i}\in V(G^{\overline{i}})$. Hence, there is a
$\\{\widehat{x},\widehat{y},\widehat{\Gamma}_{1}(w)\\}$-inclusive tree
$IT_{1}$ connects $G^{1}$ and $G^{\overline{1}}$ passing through $a_{1}b_{1}$.

Let

$T_{1}=IT_{1}\cup
P(w,\widehat{\Gamma}_{1}(w))\cup\\{x\widehat{x},y\widehat{y},xz\\}$

and let $T_{i}$ be the same as in Subcase 3.3.1 for $i\in I_{3}\cup I_{4}$.
Then $T_{1},\cdots,T_{n-1}$ are ($n-1$) IDSTs in $BP_{n}$.

Subcase 3.4. $j=\overline{k}$.

Let $W=\\{\Gamma_{i}(w)~{}|~{}i\in[n-1]\backslash\\{k\\}\\}$.

For $i\in[n-1]$, there are vertices $a_{i}$ and $b_{i}=a_{i}(1)$ in
$V(G^{\overline{n}})$ satisfying $\widehat{a}_{i}\in V(G^{i})$ and
$\widehat{b}_{i}\in V(G^{\overline{i}})$.

Since $G^{k}\backslash W$ is connected, there exists a
$\\{\widehat{z},\widehat{\Gamma}_{k}(y),w\\}$-inclusive tree $IT_{k}$ connects
$(G^{k}\backslash W)$ and $G^{\overline{k}}$ passing through $a_{k}b_{k}$. Let

$T_{k}=IT_{k}\cup P(y,\widehat{\Gamma}_{k}(y))\cup\\{xy,z\widehat{z}\\}.$

For $i\in I_{2}\cup I_{3}^{\prime}\cup I_{4}$, we can construct $T_{i}$ be the
same as in Subcase 3.3. Then $T_{1},\cdots,T_{n-1}$ are ($n-1$) IDSTs in
$BP_{n}$.

Subcase 3.5. Either $j\in I_{2}^{\prime}\cup I_{3}^{\prime}\cup I_{4}$ or
$\overline{j}\in I_{2}^{\prime}\cup I_{3}^{\prime}\cup I_{4}$.

We may construct $T_{1}$ and $T_{l}$ by analogous arguments in Subcase 3.3 and
let $T_{i}$ ($i\in[n-1]\backslash\\{1,l\\}$) by similar methods in Subcase
3.2. Then ($n-1$) IDSTs in $BP_{n}$ can be obtained. The proof is completed.
$\Box$

##  5 $\max\\{|S\cap V(G^{i})|\\}=2$ for $i\in[[n]]$

###### Lemma 5.1

For $n\geq 3$, let $BP_{n}=G^{1}\oplus G^{\overline{1}}\oplus G^{2}\oplus
G^{\overline{2}}\oplus\cdots\oplus G^{n}\oplus G^{\overline{n}}$ and
$S=\\{x,y,z,w\\}$ be any 4-subset of $V(BP_{n})$. If there are different
integers $i$ and $j$ in $[[n]]$ that $|S\cap V(G^{i})|=|S\cap V(G^{j})|=2$.
Then there exist ($n-1$) IDSTs in $BP_{n}$.

Proof Without loss of generality, we may assume that $\\{x,y\\}\subseteq
V(G^{n})$ and $\\{z,w\\}\subseteq V(G^{j})$, where
$j\in[[n]]\backslash\\{n\\}$. Furthermore, we may assume that $x=12\cdots n$.

By Lemma 2.1 and the fact that $\kappa(G^{n})=n-1$, there is a family of
($n-1$) IDPs $P_{1},\cdots,P_{n-1}$ in $G^{n}$ connecting $x$ and $y$. Without
loss of generality, assume that $x(i)\in V(P_{i})$ for $i\in[n-1]$. It is
possible that $y=x(i)$ for $i\in[n-1]$. This possibility does not affect the
following discussions. Note that $\widehat{x}(i)\in V(G^{i})$ for $i\in[n-1]$
and $\widehat{x}\in V(G^{\overline{1}})$.

Similarly, there is a family of ($n-1$) IDPs $Q_{1},\cdots,Q_{n-1}$ in $G^{j}$
connecting $z$ and $w$. For simplicity, denote $q_{i}(z)$ be the neighbour of
$z$ which belongs to $V(Q_{i})$ for $i\in[n-1]$.

Let $\mathcal{Q}=\\{\widehat{q}_{i}(z)~{}|~{}i\in[n-1]\\}$ and
$\mathcal{Q}^{\prime}=\mathcal{Q}\cup\\{\widehat{z}\\}$.

By Lemma 3.1(4), $|\mathcal{Q}^{\prime}\cap V(G^{i})|\leq 1$ for each
$i\in[[n]]$. Especially, $|\mathcal{Q}^{\prime}\cap V(G^{n})|\leq 1$. Without
loss of generality, we may assume that $\mathcal{Q}\cap V(G^{n})=\emptyset$.
We may use $\widehat{z}$ to replace $\widehat{q}_{i}(z)$ in the following
discussions if $\widehat{q}_{i}(z)\in V(G^{n})$ for $i\in[n-1]$.

Case 1. $j\notin[n-1]$.

Let $I_{s}=\\{i~{}|~{}i\in[n-1]~{}{\rm and}~{}|\mathcal{Q}\cap
V(G^{i})|=1\\}.$

Without loss of generality, we may assume that $I_{s}=\\{1,\cdots,k\\}$ and
$\widehat{q}_{i}(z)\in V(G^{i})$ for $1\leq i\leq k$. When $k<n-2$, for
$k+1\leq i\leq n-1$, we may relabel the vertices $q_{i}(z)$ that
$\widehat{q}_{i}(z)\in V(G^{m_{i}})$, where $m_{i}$ is an integer different
from $\overline{i}$.

For $1\leq i\leq k$, there is a ($\widehat{x}(i),\widehat{q}_{i}(z)$)-path
$R_{i}$ in $G^{i}$ since $G^{i}$ is connected. Moreover, for $k+1\leq i\leq
n-1$, there is a ($\widehat{x}(i),\widehat{q}_{i}(z)$)-path $R_{i}$ in
$G^{i}\cup G^{m_{i}}$ by Lemma 3.1(5) when $k<n-2$. If $k=n-2$. Set
$G^{\prime}=G^{n}\cup G^{j}\cup\big{(}\bigcup_{i=1}^{n-2}G^{i}\big{)}.$
Combined Lemma 3.1(5) with the fact that there are $n\geq 3$ clusters in
$BP_{n}\backslash G^{\prime}$, $BP_{n}\backslash G^{\prime}$ is connected.
Note that $\\{\widehat{x}(n-1),\widehat{q}_{n-1}(z)\\}\subseteq
V(G^{\prime})$. Thus, there is a
($\widehat{x}(n-1),\widehat{q}_{n-1}(z)$)-path $R_{n-1}$ in $BP_{n}\backslash
G^{\prime}$. Let

$T_{i}=P_{i}\cup Q_{i}\cup
R_{i}\cup\\{x(i)\widehat{x}(i),q_{i}(z)\widehat{q}_{i}(z)\\},\;\;\;1\leq i\leq
n-1.$

Then $T_{1},\cdots,T_{n-1}$ are ($n-1$) IDSTs in $BP_{n}$.

Case 2. $j\in[n-1]$.

To avoid duplication, we may assume that $j=n-1$.

Since $G^{n-1}$ is connected, there is a path $P$ in $G^{n-1}$ connecting
$\widehat{x}(n-1)$ and $z$. Let $v$ be the first vertex in
$V(P)\cap\Big{(}\bigcup_{i=1}^{n-1}V(Q_{i})\Big{)}$ when $P$ starts from
$\widehat{x}(n-1)$. Without loss of generality, assume that $v\in V(Q_{n-1})$.
Denote by $P(\widehat{x}(n-1),v)$ the subgraph of $P$ that starts from
$\widehat{x}(n-1)$ and ends at $v$.

Let

$T_{n-1}=P_{n-1}\cup Q_{n-1}\cup
P(\widehat{x}(n-1),v)\cup\\{x(n-1)\widehat{x}(n-1)\\}$

and construct $T_{1},\cdots,T_{n-2}$ by similar methods in Case 1. Then
$T_{1},\cdots,T_{n-1}$ are ($n-1$) IDSTs in $BP_{n}$. $\Box$

###### Lemma 5.2

For $n\geq 3$, let $BP_{n}=G^{1}\oplus G^{\overline{1}}\oplus G^{2}\oplus
G^{\overline{2}}\oplus\cdots\oplus G^{n}\oplus G^{\overline{n}}$ and
$S=\\{x,y,z,w\\}$ be any 4-subset of $V(BP_{n})$. If there are different
integers $i,j$ and $l$ in $[[n]]$ such that $|S\cap V(G^{i})|=2$ and $|S\cap
V(G^{j})|=|S\cap V(G^{l})|=1$. Then there exist ($n-1$) IDSTs in $BP_{n}$.

Proof Without loss of generality, we may assume that $\\{x,y\\}\subseteq
V(G^{n})$, $z\in V(G^{j})$ and $w\in V(G^{l})$, where $j$ and $l$ are
different integers in $[[n]]\backslash\\{n\\}$. Furthermore, let $x=12\cdots
n$.

Since $\kappa(G^{n})=n-1$, there is a family of ($n-1$) IDPs
$P_{1},\cdots,P_{n-1}$ in $G^{n}$ connecting $x$ and $y$. For simplicity,
assume that $x(i)\in V(P_{i})$ for $i\in[n-1]$. Note that $\widehat{x}\in
V(G^{\overline{1}})$ and $\widehat{x}(i)\in V(G^{i})$ for $i\in[n-1]$.

The following discussions are based on the values of $j$ and $l$.

Case 1. $\\{j,l\\}\cap[n-1]=\emptyset$.

That means
$\\{j,l\\}\subseteq\\{\overline{1},\overline{2},\cdots,\overline{n}\\}.$

Subcase 1.1. $j=\overline{n}$ or $l=\overline{n}$.

Without loss of generality, assume that $z\in V(G^{\overline{n}})$ and $w\in
V(G^{\overline{n-1}})$.

According to Lemma 3.1(5), there are ($n-1$) different vertices
$u_{1},\cdots,u_{n-1}$ in $V(G^{\overline{n}})$ that $\widehat{u}_{i}\in
V(G^{i})$ for $i\in[n-1]$. By Lemma 2.2, there is an ($n-1$)-fan
$Q_{1},\cdots,Q_{n-1}$ in $G^{\overline{n}}$ from $z$ to
$\\{u_{1},\cdots,u_{n-1}\\}$ such that $u_{i}\in V(Q_{i})$ for $i\in[n-1]$.

Likewise, there are ($n-1$) different vertices $v_{1},\cdots,v_{n-1}$ in
$V(G^{\overline{n-1}})$ that $\widehat{v}_{i}\in V(G^{i})$ for $i\in[n-2]$ and
$\widehat{v}_{n-1}\in V(G^{\overline{1}})$. Moreover, there is an ($n-1$)-fan
$R_{1},\cdots,R_{n-1}$ in $G^{\overline{n-1}}$ from $w$ to
$\\{v_{1},\cdots,v_{n-1}\\}$ such that $v_{i}\in V(R_{i})$ for $i\in[n-1]$.

By Lemma 3.1, there is a
$\\{\widehat{x}(n-1),\widehat{u}_{n-1},\widehat{v}_{n-1}\\}$-tree
$\widehat{T}_{n-1}$ in $G^{n-1}\cup G^{\overline{1}}$ and a
$\\{\widehat{x}(i),\widehat{u}_{i},\widehat{v}_{i}\\}$-tree $\widehat{T}_{i}$
in $G^{i}$, $i\in[n-2]$.

Figure 14: Illustration for Subcase 1.1

Figure 15: Illustration for Subcase 1.2

For $i\in[n-1]$, let

$\displaystyle T_{i}=\widehat{T}_{i}\cup P_{i}\cup Q_{i}\cup
R_{i}\cup\\{x(i)\widehat{x}(i),u_{i}\widehat{u}_{i},v_{i}\widehat{v}_{i}\\}.$
(8)

See Figure 15. Then $T_{1},\cdots,T_{n-1}$ are ($n-1$) IDSTs in $BP_{n}$.

Subcase 1.2. $j\neq\overline{n}$ and $l\neq\overline{n}$.

Without loss of generality, assume that $z\in V(G^{\overline{n-1}})$ and $w\in
V(G^{\overline{n-2}})$.

By Lemma 3.1, there are ($n-1$) different vertices $u_{1},\cdots,u_{n-1}$ in
$V(G^{\overline{n-1}})$ that $\widehat{u}_{i}\in V(G^{i})$ for $i\in[n-2]$ and
$\widehat{u}_{n-1}\in V(G^{\overline{n}})$. By Lemma 2.2, there is an
($n-1$)-fan $Q_{1},\cdots,Q_{n-1}$ in $G^{\overline{n-1}}$ from $z$ to
$\\{u_{1},\cdots,u_{n-1}\\}$ such that $u_{i}\in V(Q_{i})$ for $i\in[n-1]$.

Analogously, there are ($n-1$) different vertices $v_{1},\cdots,v_{n-1}$ in
$V(G^{\overline{n-2}})$ that $\widehat{v}_{i}\in V(G^{i})$ for
$i\in[n-1]\backslash\\{n-2\\}$ and $\widehat{v}_{n-2}\in V(G^{\overline{n}})$.
Moreover, there is an ($n-1$)-fan $R_{1},\cdots,R_{n-1}$ in
$G^{\overline{n-2}}$ from $w$ to $\\{v_{1},\cdots,v_{n-1}\\}$ such that
$v_{i}\in V(R_{i})$ for $i\in[n-1]$.

By Lemma 3.2, let $t_{1}$ be the neighbour of $\widehat{u}_{n-1}$ in
$V(G^{\overline{n}})$ such that $\widehat{t}_{1}\in V(G^{n-1})$. Likewise, let
$t_{2}$ be the neighbour of $\widehat{v}_{n-2}$ in $V(G^{\overline{n}})$ that
$\widehat{t}_{2}\in V(G^{n-2})$. For simplicity, denote by $L_{1}$ the path
$\\{u_{n-1}\widehat{u}_{n-1},t_{1}\widehat{u}_{n-1},t_{1}\widehat{t}_{1}\\}$
and denote by $L_{2}$ the path
$\\{v_{n-2}\widehat{v}_{n-2},t_{2}\widehat{v}_{n-2},t_{2}\widehat{t}_{2}\\}$.

Note that there is a
$\\{\widehat{x}(n-2),\widehat{u}_{n-2},\widehat{t}_{2}\\}$-tree
$\widehat{T}_{n-2}$ in $G^{n-2}$ and a
$\\{\widehat{x}(n-1),\widehat{v}_{n-1},\widehat{t}_{1}\\}$-tree
$\widehat{T}_{n-1}$ in $G^{n-1}$, respectively.

Let

$T_{n-2}=\widehat{T}_{n-2}\cup P_{n-2}\cup Q_{n-2}\cup R_{n-2}\cup
L_{2}\cup\\{x(n-2)\widehat{x}(n-2),u_{n-2}\widehat{u}_{n-2}\\}$

and

$T_{n-1}=\widehat{T}_{n-1}\cup P_{n-1}\cup Q_{n-1}\cup R_{n-1}\cup
L_{1}\cup\\{x(n-1)\widehat{x}(n-1),v_{n-1}\widehat{v}_{n-1}\\}.$

For $1\leq i\leq n-3$, let $\widehat{T}_{i}$ and $T_{i}$ be the same as in
Subcase 1.1. See Figure 15. Then $T_{1},\cdots,T_{n-1}$ are ($n-1$) IDSTs in
$BP_{n}$.

Case 2. $|\\{j,l\\}\cap[n-1]|=1$.

Without loss of generality, we may assume that $j=n-1$. That means $z\in
V(G^{n-1})$.

There exist ($n-2$) different vertices $u_{1},\cdots,u_{n-2}$ in
$V(G^{n-1})\backslash\\{\widehat{x}(n-1)\\}$ such that $\widehat{u}_{i}\in
V(G^{i})$ for $i\in[n-2]$. By Lemma 2.2, there is an ($n-1$)-fan
$Q_{1},\cdots,Q_{n-1}$ in $G^{n-1}$ from $z$ to
$\\{u_{1},\cdots,u_{n-2},\widehat{x}(n-1)\\}$ such that $u_{i}\in V(Q_{i})$
for $i\in[n-2]$ and $\widehat{x}(n-1)\in V(Q_{n-1})$.

Subcase 2.1. $l=\overline{1}$, i.e., $w\in V(G^{\overline{1}})$.

There exist ($n-2$) different vertices $v_{1},\cdots,v_{n-2}$ in
$V(G^{\overline{1}})\backslash\\{\widehat{x}\\}$ such that $\widehat{v}_{i}\in
V(G^{i})$ for $2\leq i\leq n-2$ and $\widehat{v}_{1}\in V(G^{\overline{n}})$.
Furthermore, there is an ($n-1$)-fan $R_{1},\cdots,R_{n-1}$ in
$G^{\overline{1}}$ from $w$ to $\\{v_{1},\cdots,v_{n-2},\widehat{x}\\}$ such
that $v_{i}\in V(R_{i})$ for $i\in[n-2]$ and $\widehat{x}\in V(R_{n-1})$.

Let $T_{n-1}=P_{n-1}\cup Q_{n-1}\cup
R_{n-1}\cup\\{x\widehat{x},x(n-1)\widehat{x}(n-1)\\}$.

Note that there is a
$\\{\widehat{x}(1),\widehat{u}_{1},\widehat{v}_{1}\\}$-tree $\widehat{T}_{1}$
in $G^{1}\cup G^{\overline{n}}$ and a
$\\{\widehat{x}(i),\widehat{u}_{i},\widehat{v}_{i}\\}$-tree $\widehat{T}_{i}$
in $G^{i}$ for $2\leq i\leq n-2$. We may construct $T_{1},\cdots,T_{n-2}$ be
the same as in Eq.(8). See Figure 17. Then ($n-1$) IDSTs
$T_{1},\cdots,T_{n-1}$ can be obtained.

Figure 16: Illustration for Subcase 2.1

Figure 17: Illustration for Subcase 2.2

Subcase 2.2. $l\neq\overline{1}$.

To avoid duplication, we consider the case that $l=\overline{n}$. It follows
that $w\in V(G^{\overline{n}})$.

There are ($n-1$) different vertices $v_{1},\cdots,v_{n-1}$ in
$V(G^{\overline{n}})$ such that $\widehat{v}_{i}\in V(G^{i})$ for $i\in[n-2]$
and $\widehat{v}_{n-1}\in V(G^{\overline{1}})$. Furthermore, there is an
($n-1$)-fan $R_{1},\cdots,R_{n-1}$ in $G^{\overline{n}}$ from $w$ to
$\\{v_{1},\cdots,v_{n-1}\\}$ such that $v_{i}\in V(R_{i})$ for $i\in[n-1]$.
Moreover, there is a ($\widehat{x},\widehat{v}_{n-1}$)-path $P^{\prime}$ in
$G^{\overline{1}}$ since $G^{\overline{1}}$ is connected.

Let $T_{n-1}=P_{n-1}\cup Q_{n-1}\cup R_{n-1}\cup
P^{\prime}\cup\\{x\widehat{x},x(n-1)\widehat{x}(n-1),v_{n-1}\widehat{v}_{n-1}\\}$
and $T_{i}$ be the same as in Eq.(8) for $i\in[n-2]$. See Figure 17. Then
$T_{1},\cdots,T_{n-1}$ are ($n-1$) IDSTs in $BP_{n}$.

Case 3. $|\\{j,l\\}\cap[n-1]|=2$, i.e., $\\{j,l\\}\subseteq[n-1]$.

Without loss of generality, we may assume that $j=1$ and $l=2$.

There are ($n-2$) vertices $u_{i}$ in $V(G^{1})\backslash\\{\widehat{x}(1)\\}$
such that $\widehat{u}_{i}\in V(G^{i})$ for $2\leq i\leq n-1$. By Lemma 2.2,
there is an ($n-1$)-fan $Q_{1},\cdots,Q_{n-1}$ in $G^{1}$ from $z$ to
$\\{\widehat{x}(1),u_{2},\cdots,u_{n-1}\\}$ such that $\widehat{x}(1)\in
V(Q_{1})$ and $u_{i}\in V(Q_{i})$ for $2\leq i\leq n-1$.

Set $G^{\prime}=BP_{n}\backslash\big{(}\bigcup_{i=1}^{n}V(G^{i})\big{)}$. In
order to obtain ($n-1$) IDSTs in $BP_{n}$, the following discussions are made
according to the location of $\widehat{w}$.

Subcase 3.1. $\widehat{w}\in V(G^{\prime})$.

There exist ($n-3$) different vertices $v_{3},\cdots,v_{n-1}$ in
$V(G^{2})\backslash\\{\widehat{x}(2),\widehat{u}_{2}\\}$ such that
$\widehat{v}_{i}\in V(G^{i})$ for $3\leq i\leq n-1$. By Lemma 2.2, there is an
($n-1$)-fan $R_{1},\cdots,R_{n-1}$ in $G^{2}$ from $w$ to
$\\{\widehat{u}_{2},\widehat{x}(2),v_{3},\cdots,v_{n-1}\\}$ such that
$\widehat{u}_{2}\in V(R_{1})$, $\widehat{x}(2)\in V(R_{2})$ and $v_{i}\in
V(R_{i})$ for $3\leq i\leq n-1$.

For $3\leq i\leq n-1$, there is a
$\\{\widehat{x}(i),\widehat{v}_{i},\widehat{u}_{i}\\}$-tree $\widehat{T}_{i}$
in $G^{i}$ since
$\\{\widehat{x}(i),\widehat{v}_{i},\widehat{u}_{i}\\}\subseteq V(G^{i})$,
thus, let $T_{i}$ be the same as in Eq.(8).

It is seen that there is a ($\widehat{x},\widehat{w}$)-path $L_{1}$ in
$G^{\prime}$ by Lemma 3.1(5). Let $T_{2}=P_{2}\cup R_{2}\cup R_{1}\cup
Q_{2}\cup\\{x(2)\widehat{x}(2),u_{2}\widehat{u}_{2}\\}$ and $T_{1}=P_{1}\cup
L_{1}\cup Q_{1}\cup\\{x\widehat{x},x(1)\widehat{x}(1),w\widehat{w}\\}$. See
Figure 19. Then $T_{1},\cdots,T_{n-1}$ are ($n-1$) IDSTs in $BP_{n}$.

Figure 18: Illustration for Subcase 3.1

Figure 19: Illustration for Subcase 3.2

Subcase 3.2. $\widehat{w}\in V(G^{i})$, for $i\in[n-1]\backslash\\{2\\}$.

Without loss of generality, we may assume that $\widehat{w}\in V(G^{1})$. Let
$u_{2}=\widehat{w}$ in former discussions. Then $\widehat{w}\in V(Q_{2})$.

We can find ($n-2$) vertices $a,v_{3},\cdots,v_{n-1}$ in
$V(G^{2})\backslash\\{\widehat{x}(2)\\}$ such that $\widehat{a}\in
V(G^{\overline{1}})$ and $\widehat{v}_{i}\in V(G^{i})$ for $3\leq i\leq n-1$.
By Lemma 2.2, there is an ($n-1$)-fan $R_{1},\cdots,R_{n-1}$ in $G^{2}$ from
$w$ to $\\{a,\widehat{x}(2),v_{3},\cdots,v_{n-1}\\}$ that $a\in V(R_{1})$,
$\widehat{x}(2)\in V(R_{2})$ and $v_{i}\in V(R_{i})$ for $3\leq i\leq n-1$.
Moreover, there is a ($\widehat{x},\widehat{a}$)-path $L_{1}$ in
$G^{\overline{1}}$.

Let $T_{2}=P_{2}\cup R_{2}\cup
Q_{2}\cup\\{x(2)\widehat{x}(2),w\widehat{w}\\}$, $T_{1}=P_{1}\cup L_{1}\cup
Q_{1}\cup R_{1}\cup\\{x\widehat{x},x(1)\widehat{x}(1),a\widehat{a}\\}$ and
$T_{i}$ ($3\leq i\leq n-1$) be the same as in Eq.(8). See Figure 19. Then
$T_{1},\cdots,T_{n-1}$ are ($n-1$) IDSTs in $BP_{n}$.

Subcase 3.3. $\widehat{w}\in V(G^{n})$.

Since $G^{n}$ is connected, there is a path $\widetilde{P}$ in $G^{n}$
connecting $\widehat{w}$ and $x$. Let $v$ be the first vertex in
$V(\widetilde{P})\cap\big{(}\bigcup_{i=1}^{n-1}V(P_{i})\big{)}$ when
$\widetilde{P}$ starts from $\widehat{w}$. Denote by
$\widetilde{P}(\widehat{w},v)$ the subgraph of $\widetilde{P}$ that starts
from $\widehat{w}$ and ends at $v$.

Subcase 3.3.1. $v\in V(P_{1})$.

Let $T_{1}=P_{1}\cup
Q_{1}\cup\widetilde{P}(\widehat{w},v)\cup\\{w\widehat{w},x(1)\widehat{x}(1)\\}$
and $T_{i}$ be the same as in Subcase 3.1 for $2\leq i\leq n-1$. Then
$T_{1},\cdots,T_{n-1}$ are ($n-1$) IDSTs in $BP_{n}$.

Subcase 3.3.2. $v\in V(P_{2})$.

There are ($n-2$) vertices $a,v_{3},\cdots,v_{n-1}$ in
$V(G^{2})\backslash\\{\widehat{x}(2),\widehat{u}_{2}\\}$ such that
$\widehat{a}\in V(G^{\overline{1}})$ and $\widehat{v}_{i}\in V(G^{i})$ for
$3\leq i\leq n-1$. Furthermore, there is an ($n-1$)-fan $R_{1},\cdots,R_{n-1}$
in $G^{2}$ from $w$ to $\\{\widehat{u}_{2},a,v_{3},\cdots,v_{n-1}\\}$ that
$\widehat{u}_{2}\in V(R_{1})$, $a\in V(R_{2})$ and $v_{i}\in V(R_{i})$ for
$3\leq i\leq n-1$. Moreover, there is a ($\widehat{x},\widehat{a}$)-path
$L_{1}$ in $G^{\overline{1}}$.

Let $T_{2}=P_{2}\cup R_{1}\cup
Q_{2}\cup\widetilde{P}(\widehat{w},v)\cup\\{u_{2}\widehat{u}_{2},w\widehat{w}\\}$,
$T_{1}=P_{1}\cup L_{1}\cup Q_{1}\cup
R_{2}\cup\\{x\widehat{x},x(1)\widehat{x}(1),a\widehat{a}\\}$ and $T_{i}$
($3\leq i\leq n-1$) be the same as in Eq.(8). See Figure 21. Then
$T_{1},\cdots,T_{n-1}$ are ($n-1$) IDSTs in $BP_{n}$.

Figure 20: Illustration for Subcase 3.3.2

Figure 21: Illustration for Subcase 3.3.3

Subcase 3.3.3. $v\in V(P_{i})$ for $3\leq i\leq n-1$.

Without loss of generality, we may assume that $v\in V(P_{3})$.

There are ($n-3$) vertices $a,v_{4},\cdots,v_{n-1}$ in
$V(G^{2})\backslash\\{\widehat{u}_{2},\widehat{x}(2)\\}$ such that
$\widehat{a}\in V(G^{\overline{1}})$ and $\widehat{v}_{i}\in V(G^{i})$ for
$4\leq i\leq n-1$. Moreover, there is an ($n-1$)-fan $R_{1},\cdots,R_{n-1}$ in
$G^{2}$ from $w$ to
$\\{\widehat{u}_{2},\widehat{x}(2),a,v_{4},\cdots,v_{n-1}\\}$ that
$\widehat{u}_{2}\in V(R_{1})$, $\widehat{x}(2)\in V(R_{2})$, $a\in V(R_{3})$
and $v_{i}\in V(R_{i})$ for $4\leq i\leq n-1$.

Since $G^{i}$ is connected for each $i\in[[n]]$, there is a
($\widehat{x},\widehat{a}$)-path $L_{1}$ in $G^{\overline{1}}$ and a
($\widehat{x}(3),\widehat{u}_{3}$)-path $L_{3}$ in $G^{3}$, respectively.

Let

$T_{3}^{\prime}=P_{3}\cup\widetilde{P}(\widehat{w},v)\cup L_{3}\cup
Q_{3}\cup\\{x(3)\widehat{x}(3),u_{3}\widehat{u}_{3},w\widehat{w}\\},$
$T_{2}=P_{2}\cup R_{2}\cup R_{1}\cup
Q_{2}\cup\\{u_{2}\widehat{u}_{2},x(2)\widehat{x}(2)\\}$

and

$T_{1}=P_{1}\cup L_{1}\cup Q_{1}\cup
R_{3}\cup\\{x\widehat{x},x(1)\widehat{x}(1),a\widehat{a}\\}.$

For $4\leq i\leq n-1$, let $\widehat{T}_{i}$ and $T_{i}$ be the same as in
Eq.(8). See Figure 21. Then $T_{1},T_{2},T_{3}^{\prime},T_{4},\cdots,T_{n-1}$
are ($n-1$) IDSTs in $BP_{n}$. $\Box$

##  6 $|S\cap V(G^{i})|\leq 1$ for each $i\in[[n]]$

###### Lemma 6.1

For $n\geq 3$, let $BP_{n}=G^{1}\oplus G^{\overline{1}}\oplus G^{2}\oplus
G^{\overline{2}}\oplus\cdots\oplus G^{n}\oplus G^{\overline{n}}$ and
$S=\\{x,y,z,w\\}$ be any 4-subset of $V(BP_{n})$. If $|S\cap V(G^{i})|\leq 1$
for any integer $i\in[[n]]$. Then there exist ($n-1$) IDSTs in $BP_{n}$.

Proof Without loss of generality, we may assume that $x\in V(G^{r})$, $y\in
V(G^{k})$, $z\in V(G^{l})$ and $w\in V(G^{m})$, where
$\\{r,k,l,m\\}\subseteq[[n]]$.

Case 1. $n\geq 7$.

Since $2n-8\geq n-1$ for $n\geq 7$, there exist ($n-1$) different integers
$h_{1},\cdots,h_{n-1}$ in
$[[n]]\backslash\\{r,k,l,m,\bar{r},\bar{k},\bar{l},\bar{m}\\}$. By Lemma 3.1,
we may choose ($n-1$) vertices $a_{i}\in V(G^{r})$ that $\widehat{a}_{i}\in
V(G^{h_{i}})$ for $i\in[n-1]$. Analogously, for $i\in[n-1]$, there are ($n-1$)
vertices $b_{i}\in V(G^{k})$ that $\widehat{b}_{i}\in V(G^{h_{i}})$, there are
($n-1$) vertices $c_{i}\in V(G^{l})$ that $\widehat{c}_{i}\in V(G^{h_{i}})$
and ($n-1$) vertices $d_{i}\in V(G^{m})$ that $\widehat{d}_{i}\in
V(G^{h_{i}})$.

Since $G^{h_{i}}$ is connected, there is a
$\\{\widehat{a}_{i},\widehat{b}_{i},\widehat{c}_{i},\widehat{d}_{i}\\}$-tree
$\widehat{T}_{i}$ in $G^{h_{i}}$ for $i\in[n-1]$.

Let $A=\\{a_{1},\cdots,a_{n-1}\\}$, $B=\\{b_{1},\cdots,b_{n-1}\\}$,
$C=\\{c_{1},\cdots,c_{n-1}\\}$ and $D=\\{d_{1},\cdots,d_{n-1}\\}$. Obviously,
$|A|=|B|=|C|=|D|=n-1$. By Lemma 2.2 and Lemma 3.1(2), there is an ($n-1$)-fan
$P_{1},\cdots,P_{n-1}$ in $G^{r}$ from $x$ to $A$ such that $a_{i}\in
V(P_{i})$ for $i\in[n-1]$. Similarly, for $i\in[n-1]$, there is an ($n-1$)-fan
$Q_{1},\cdots,Q_{n-1}$ in $G^{k}$ from $y$ to $B$ such that $b_{i}\in
V(Q_{i})$, there is an ($n-1$)-fan $R_{1},\cdots,R_{n-1}$ in $G^{l}$ from $z$
to $C$ such that $c_{i}\in V(R_{i})$ and an ($n-1$)-fan $L_{1},\cdots,L_{n-1}$
in $G^{m}$ from $w$ to $D$ such that $d_{i}\in V(L_{i})$.

For $i\in[n-1]$, let

$T_{i}=\widehat{T}_{i}\cup P_{i}\cup Q_{i}\cup R_{i}\cup
L_{i}\cup\\{a_{i}\widehat{a}_{i},b_{i}\widehat{b}_{i},c_{i}\widehat{c}_{i},d_{i}\widehat{d}_{i}\\}.$

Then $T_{1},\cdots,T_{n-1}$ are ($n-1$) IDSTs in $BP_{n}$.

Case 2. $n=6$.

Subcase 2.1. There exist two integers $i$ and $j$ in $\\{r,k,l,m\\}$ that
$i+j=0$.

Without loss of generality, assume that $r=1$ and $k=\overline{1}$. Since
$2n-6>n-1$ for $n=6$, there exist five integers $h_{1},\cdots,h_{5}$ in
$[[n]]\backslash\\{1,\overline{1},l,\overline{l},m,\overline{m}\\}$. By
similar methods in Case 1, we may construct ($n-1$) IDSTs in $BP_{n}$.

Subcase 2.2. For any two integers $i$ and $j$ in $\\{r,k,l,m\\}$, it has
$i+j\neq 0$.

Without loss of generality, we may assume that $x\in V(G^{1})$, $y\in
V(G^{2})$, $z\in V(G^{3})$ and $w\in V(G^{4})$.

By Lemma 3.1, there are five vertices $a_{1},\cdots,a_{5}$ in $V(G^{1})$ that
$\widehat{a}_{1}\in V(G^{\overline{2}})$, $\widehat{a}_{2}\in V(G^{5})$,
$\widehat{a}_{3}\in V(G^{\overline{5}})$, $\widehat{a}_{4}\in V(G^{6})$ and
$\widehat{a}_{5}\in V(G^{\overline{6}})$. Furthermore, there are different
vertices $\\{b_{1},\cdots,b_{5}\\}\subseteq V(G^{2})$,
$\\{c_{1},\cdots,c_{5}\\}\subseteq V(G^{3})$ and
$\\{d_{1},\cdots,d_{5}\\}\subseteq V(G^{4})$ satisfying
$\\{\widehat{b}_{1},\widehat{c}_{1},\widehat{d}_{1}\\}\subseteq
V(G^{\overline{1}})$,
$\\{\widehat{b}_{2},\widehat{c}_{2},\widehat{d}_{2}\\}\subseteq V(G^{5})$,
$\\{\widehat{b}_{3},\widehat{c}_{3},\widehat{d}_{3}\\}\subseteq
V(G^{\overline{5}})$,
$\\{\widehat{b}_{4},\widehat{c}_{4},\widehat{d}_{4}\\}\subseteq V(G^{6})$ and
$\\{\widehat{b}_{5},\widehat{c}_{5},\widehat{d}_{5}\\}\subseteq
V(G^{\overline{6}})$.

By Lemma 3.1(5), there is a
$\\{\widehat{a}_{1},\widehat{b}_{1},\widehat{c}_{1},\widehat{d}_{1}\\}$-tree
$\widehat{T}_{1}$ in $G^{\overline{1}}\cup G^{\overline{2}}$. Furthermore,
there is a
$\\{\widehat{a}_{2},\widehat{b}_{2},\widehat{c}_{2},\widehat{d}_{2}\\}$-tree
$\widehat{T}_{2}$ in $G^{5}$, a
$\\{\widehat{a}_{3},\widehat{b}_{3},\widehat{c}_{3},\widehat{d}_{3}\\}$-tree
$\widehat{T}_{3}$ in $G^{\overline{5}}$, a
$\\{\widehat{a}_{4},\widehat{b}_{4},\widehat{c}_{4},\widehat{d}_{4}\\}$-tree
$\widehat{T}_{4}$ in $G^{6}$ and a
$\\{\widehat{a}_{5},\widehat{b}_{5},\widehat{c}_{5},\widehat{d}_{5}\\}$-tree
$\widehat{T}_{5}$ in $G^{\overline{6}}$, respectively.

For $1\leq i\leq 5$, we may define $P_{i}$, $Q_{i}$, $R_{i}$, $L_{i}$ and
$T_{i}$ be the same as in Case 1. Then $T_{1},\cdots,T_{5}$ are five IDSTs in
$BP_{n}$.

Case 3. $n=5$.

Subcase 3.1. There exist two integers $i$ and $j$ in $\\{r,k,l,m\\}$ that
$i+j=0$.

By similar methods in Subcase 2.1, four IDSTs in $BP_{n}$ can be constructed
and the proof is omitted here.

Subcase 3.2. For any two integers $i$ and $j$ in $\\{r,k,l,m\\}$, it has
$i+j\neq 0$.

Without loss of generality, we may assume that $x\in V(G^{1})$, $y\in
V(G^{2})$, $z\in V(G^{3})$ and $w\in V(G^{4})$.

By Lemma 3.1, there are four vertices $a_{1},a_{2},a_{3},a_{4}$ in $V(G^{1})$
that $\widehat{a}_{1}\in V(G^{\overline{2}})$, $\widehat{a}_{2}\in
V(G^{\overline{3}})$, $\widehat{a}_{3}\in V(G^{5})$ and $\widehat{a}_{4}\in
V(G^{\overline{5}})$. Moreover, there are vertices
$\\{b_{1},\cdots,b_{4}\\}\subseteq V(G^{2})$,
$\\{c_{1},\cdots,c_{4}\\}\subseteq V(G^{3})$ and
$\\{d_{1},\cdots,d_{4}\\}\subseteq V(G^{4})$ satisfying
$\\{\widehat{b}_{1},\widehat{c}_{1},\widehat{d}_{1}\\}\subseteq
V(G^{\overline{1}})$,
$\\{\widehat{b}_{2},\widehat{c}_{2},\widehat{d}_{2}\\}\subseteq
V(G^{\overline{3}})\cup V(G^{\overline{4}})$,
$\\{\widehat{b}_{3},\widehat{c}_{3},\widehat{d}_{3}\\}\subseteq V(G^{5})$ and
$\\{\widehat{b}_{4},\widehat{c}_{4},\widehat{d}_{4}\\}\subseteq
V(G^{\overline{5}})$.

Since $G^{\overline{2i-1}}\cup G^{\overline{2i}}$ is connected, there is a
$\\{\widehat{a}_{i},\widehat{b}_{i},\widehat{c}_{i},\widehat{d}_{i}\\}$-tree
$\widehat{T}_{i}$ in $G^{\overline{2i-1}}\cup G^{\overline{2i}}$ for $1\leq
i\leq 2$. Moreover, there is a
$\\{\widehat{a}_{3},\widehat{b}_{3},\widehat{c}_{3},\widehat{d}_{3}\\}$-tree
$\widehat{T}_{3}$ in $G^{5}$ and a
$\\{\widehat{a}_{4},\widehat{b}_{4},\widehat{c}_{4},\widehat{d}_{4}\\}$-tree
$\widehat{T}_{4}$ in $G^{\overline{5}}$, respectively.

For $1\leq i\leq 4$, we may define $P_{i}$, $Q_{i}$, $R_{i}$, $L_{i}$ and
$T_{i}$ be the same as in Case 1. Then $T_{1},\cdots,T_{4}$ are four IDSTs in
$BP_{n}$.

Case 4. $n=4$.

Subcase 4.1. There exist two pairs of integers in $\\{r,k,l,m\\}$ that their
sum is 0.

By similar arguments in Subcase 2.1, three IDSTs can be constructed and the
details are omitted.

Subcase 4.2. There are exactly two integers $i$ and $j$ in $\\{r,k,l,m\\}$
that $i+j=0$.

Without loss of generality, we may assume that $x\in V(G^{1})$, $y\in
V(G^{\overline{1}})$, $z\in V(G^{2})$ and $w\in V(G^{3})$.

By Lemma 3.1, there are different vertices $\\{a_{1},a_{2},a_{3}\\}\subseteq
V(G^{1})$, $\\{b_{1},b_{2},b_{3}\\}\subseteq V(G^{\overline{1}})$,
$\\{c_{1},c_{2},c_{3}\\}\subseteq V(G^{2})$ and
$\\{d_{1},d_{2},d_{3}\\}\subseteq V(G^{3})$ that
$\\{\widehat{a}_{1},\widehat{b}_{1},\widehat{c}_{1},\widehat{d}_{1}\\}\subseteq
V(G^{\overline{2}})\cup V(G^{\overline{3}})$,
$\\{\widehat{a}_{2},\widehat{b}_{2},\widehat{c}_{2},\widehat{d}_{2}\\}\subseteq
V(G^{4})$ and
$\\{\widehat{a}_{3},\widehat{b}_{3},\widehat{c}_{3},\widehat{d}_{3}\\}\subseteq
V(G^{\overline{4}})$.

According to Lemma 3.1(5), there is
$\\{\widehat{a}_{1},\widehat{b}_{1},\widehat{c}_{1},\widehat{d}_{1}\\}$-tree
$\widehat{T}_{1}$ in $G^{\overline{2}}\cup G^{\overline{3}}$ since
$G^{\overline{2}}\cup G^{\overline{3}}$ is connected. Moreover, there is a
$\\{\widehat{a}_{2},\widehat{b}_{2},\widehat{c}_{2},\widehat{d}_{2}\\}$-tree
$\widehat{T}_{2}$ in $G^{4}$ and a
$\\{\widehat{a}_{3},\widehat{b}_{3},\widehat{c}_{3},\widehat{d}_{3}\\}$-tree
$\widehat{T}_{3}$ in $G^{\overline{4}}$, respectively. For $1\leq i\leq 3$,
let $P_{i}$, $Q_{i}$, $R_{i}$, $L_{i}$ and $T_{i}$ be the same as in Case 1.
Then three IDSTs are constructed.

Subcase 4.3. For any two integers $i$ and $j$ in $\\{r,k,l,m\\}$, it has
$i+j\neq 0$.

Without loss of generality, we may assume that $x\in V(G^{1})$, $y\in
V(G^{2})$, $z\in V(G^{3})$ and $w\in V(G^{4})$.

Based on Lemma 3.2, there exists an integer
$i\in[[4]]\backslash\\{1,\overline{1}\\}$ that $\widehat{x}\in V(G^{i})$ and
$\widehat{x}(1)\in V(G^{\overline{i}})$. Without loss of generality, assume
that $i=2$. That is to say, $\widehat{x}\in V(G^{2})$ and $\widehat{x}(1)\in
V(G^{\overline{2}})$. For convenience, denote by $\widehat{x}(1)=g$. Note that
$\widehat{g}(1)\in V(G^{\overline{1}})$. There exist two vertices $a_{2}$ and
$a_{3}$ in $V(G^{1})\backslash\\{x,x(1)\\}$ that $\widehat{a}_{i}\in
V(G^{\overline{i}})$ for $i\in\\{2,3\\}$. This is possible since $(n-2)!\times
2^{n-2}>2$ when $n=4$.

There exist two vertices $b_{1}$ and $b_{3}$ in
$V(G^{2})\backslash\\{\widehat{x}\\}$ that $\widehat{b}_{i}\in
V(G^{\overline{i}})$ for $i\in\\{1,3\\}$. Moreover, there are three vertices
$\\{c_{1},c_{2},c_{3}\\}\subseteq V(G^{3})$ that $\widehat{c}_{i}\in
V(G^{\overline{i}})$ for $i\in\\{1,2\\}$ and $\widehat{c}_{3}\in
V(G^{\overline{4}})$ and three vertices $\\{d_{1},d_{2},d_{3}\\}\subseteq
V(G^{4})$ that $\widehat{d}_{i}\in V(G^{\overline{i}})$ where
$i\in\\{1,2,3\\}$.

Figure 22: Illustration for Subcase 4.3

Based on Lemma 3.3, $G^{\overline{2}}\backslash\\{g,g(1)\\}$ is still
connected. Thus, we can find a
$\\{\widehat{a}_{2},\widehat{c}_{2},\widehat{d}_{2}\\}$-tree $\widehat{T}_{2}$
in $G^{\overline{2}}\backslash\\{g,g(1)\\}$. Moreover, there is a
$\\{\widehat{b}_{1},\widehat{c}_{1},\widehat{d}_{1},\widehat{g}(1)\\}$-tree
$\widehat{T}_{1}$ in $G^{\overline{1}}$ and a
$\\{\widehat{a}_{3},\widehat{b}_{3},\widehat{c}_{3},\widehat{d}_{3}\\}$-tree
$\widehat{T}_{3}$ in $G^{\overline{3}}\cup G^{\overline{4}}$.

Remind that $\kappa(G^{i})=3$ for $1\leq i\leq 4$, there is a 3-fan
$P_{1},P_{2}$ and $P_{3}$ in $G^{1}$ from $x$ to $\\{x(1),a_{2},a_{3}\\}$ that
$x(1)\in V(P_{1})$ and $a_{i}\in V(P_{i})$ for $i\in\\{2,3\\}$. There is a
3-fan $Q_{1},Q_{2}$ and $Q_{3}$ in $G^{2}$ from $y$ to
$\\{\widehat{x},b_{1},b_{3}\\}$ that $\widehat{x}\in V(Q_{2})$ and $b_{i}\in
V(Q_{i})$ for $i\in\\{1,3\\}$. There is a 3-fan $R_{1},R_{2}$ and $R_{3}$ in
$G^{3}$ from $z$ to $\\{c_{1},c_{2},c_{3}\\}$ that $c_{i}\in V(R_{i})$ and a
3-fan $L_{1},L_{2}$ and $L_{3}$ in $G^{4}$ from $w$ to
$\\{d_{1},d_{2},d_{3}\\}$ that $d_{i}\in V(L_{i})$ for $1\leq i\leq 3$.

Let

$T_{1}=\widehat{T}_{1}\cup P_{1}\cup Q_{1}\cup R_{1}\cup
L_{1}\cup\\{x(1)g,gg(1),g(1)\widehat{g}(1),b_{1}\widehat{b}_{1},c_{1}\widehat{c}_{1},d_{1}\widehat{d}_{1}\\},$
$T_{2}=\widehat{T}_{2}\cup P_{2}\cup Q_{2}\cup R_{2}\cup
L_{2}\cup\\{x\widehat{x},a_{2}\widehat{a}_{2},c_{2}\widehat{c}_{2},d_{2}\widehat{d}_{2}\\}$

and $T_{3}=\widehat{T}_{3}\cup P_{3}\cup Q_{3}\cup R_{3}\cup
L_{3}\cup\\{a_{3}\widehat{a}_{3},b_{3}\widehat{b}_{3},c_{3}\widehat{c}_{3},d_{3}\widehat{d}_{3}\\}.$
See Figure 22. It is seen that $T_{1},T_{2}$ and $T_{3}$ are three IDSTs in
$BP_{n}$.

Case 5. $n=3$.

Subcase 5.1. There exist two pairs of integers in $\\{r,k,l,m\\}$ that their
sum is 0.

By similar arguments in Subcase 2.1, two IDSTs can be constructed.

Subcase 5.2. There are exactly two integers $i$ and $j$ in $\\{r,k,l,m\\}$
that $i+j=0$.

Without loss of generality, we may assume that $x\in V(G^{1})$, $y\in
V(G^{\overline{1}})$, $z\in V(G^{2})$ and $w\in V(G^{3})$.

Figure 23: The subgraph $H$

Figure 24: The subgraph $H^{\prime}$

Let $H=G^{1}\cup G^{\overline{1}}\cup G^{2}\cup G^{3}$ and
$H^{\prime}=BP_{3}\backslash H$. See Figure 24 and Figure 24. The following
Claims 1 and 2 can be derived easily.

Claim 1. Both $H$ and $H^{\prime}$ are connected.

Claim 2. For $i\in\\{\overline{1},1,2,3\\}$, let $a_{i}$ be any vertex in
$V(G^{i})$. Then $H\backslash\\{a_{\overline{1}},a_{1},a_{2},a_{3}\\}$ is
connected.

Let $p_{1}=\bar{3}\bar{1}2$, $p_{2}=3\bar{1}2$, $p_{3}=\bar{3}12$,
$p_{4}=312$, $p_{5}=\bar{2}13$, $p_{6}=213$, $p_{7}=\bar{2}\bar{1}3$ and
$p_{8}=2\bar{1}3$ be eight vertices in $V(H)$. Moreover, let
$F_{1}=\\{p_{1},p_{2}\\}$, $F_{2}=\\{p_{3},p_{4}\\}$,
$F_{3}=\\{p_{5},p_{6}\\}$ and $F_{4}=\\{p_{7},p_{8}\\}$ be 2-subsets of
$V(H)$.

Claim 3. For $i\in\\{1,\overline{1}\\}$, let $a_{i}$ be any vertex in
$V(G^{i})$. Let $V_{1}$ be a 2-subset of $V(G^{2})$ that
$V_{1}\in\\{F_{1},F_{2}\\}$ and $V_{2}$ be a 2-subset of $V(G^{3})$ that
$V_{2}\in\\{F_{3},F_{4}\\}$. Then
$H\backslash\Big{(}\\{a_{\overline{1}},a_{1}\\}\cup V_{1}\cup V_{2}\Big{)}$ is
connected.

Proof of Claim 3. Note that $d_{H}(p_{2i})=2$ for $i\in[4]$. By Claim 2,
$H\backslash\\{a_{\overline{1}},a_{1},a_{2},a_{3}\\}$ is connected for
$a_{2}\in\\{p_{1},p_{3}\\}$, $a_{3}\in\\{p_{5},p_{7}\\}$ and $a_{i}\in
V(G^{i})$ for $i\in\\{1,\overline{1}\\}$. It is seen that
$H\backslash\Big{(}\\{a_{\overline{1}},a_{1}\\}\cup V_{1}\cup V_{2}\Big{)}$ is
obtained from $H\backslash\\{a_{\overline{1}},a_{1},a_{2},a_{3}\\}$ by
deleting two vertices of degree one. Thus,
$H\backslash\Big{(}\\{a_{\overline{1}},a_{1}\\}\cup V_{1}\cup V_{2}\Big{)}$ is
connected. $\Box$

For $x\in V(G^{1})$ and $1\leq i\leq 2$, we can see that either $\widehat{x}$
or $\widehat{x}(i)$ belong to $V(H^{\prime})$. Let

$P_{1}(x)=\left\\{\begin{array}[]{ll}x\widehat{x},&{\rm if}~{}\widehat{x}\in
V(H^{\prime}),\\\ \\{xx(i),x(i)\widehat{x}(i)\\},&{\rm if}~{}\widehat{x}(i)\in
V(H^{\prime}).\end{array}\right.$

We say that $P_{1}(x)$ is a type-1-path of $x$. Likewise, there is a
type-1-path $P_{1}(y)$ of $y\in V(G^{\overline{1}})$.

For $z\in V(G^{2})$, it is not difficult to check that there is a type-1-path
of $z$ if $z\notin\\{132,\bar{1}32\\}$. If $z=132$, denote by $P_{2}(z)$ the
path $\\{zp_{1},p_{1}p_{2},p_{2}\widehat{p}_{2}\\}$. Furthermore, denote by
$P_{2}(z)$ the path $\\{zp_{3},p_{3}p_{4},p_{4}\widehat{p}_{4}\\}$ if
$z=\bar{1}32$. We say that $P_{2}(z)$ is a type-2-path of $z$.

For a vertex $a\in V(H)$ and $1\leq i\leq 2$, denote by $IP_{i}(a)$ the set of
interior vertices of $P_{i}(a)$, denote by $TP_{i}(a)$ the terminal vertex of
$P_{i}(a)$ in $H^{\prime}$. Note that $|IP_{1}(a)|\leq 1$ for each $a\in
V(H)$. In addition, $IP_{2}(z)\in\\{F_{1},F_{2}\\}$ if
$z\in\\{132,\bar{1}32\\}$.

Likewise, there is either a type-1-path $P_{1}(w)$ or a type-2-path $P_{2}(w)$
of $w\in V(G^{3})$ such that $IP_{2}(w)\in\\{F_{3},F_{4}\\}.$ Combined with
Claims 1, 2 and 3, there is an $S$-tree $T_{1}$ in
$H\backslash\\{IP_{1}(x),IP_{1}(y),IP_{i}(z),IP_{j}(w)\\}$ and a
$\\{TP_{1}(x),TP_{1}(y),TP_{i}(z),TP_{j}(w)\\}$-tree $\widehat{T}_{2}$ in
$H^{\prime}$, $1\leq i\leq 2$ and $1\leq j\leq 2$. Let

$T_{2}=\widehat{T}_{2}\cup P_{1}(x)\cup P_{1}(y)\cup P_{i}(z)\cup
P_{j}(w),\;\;1\leq i\leq 2,1\leq j\leq 2.$

Then $T_{1}$ and $T_{2}$ are two desired IDSTs in $BP_{3}$. The proof is done.
$\Box$

##  7 The generalized 4-connectivity of the burnt pancake graph

Now, we are prepared to prove Theorem 1.1, the main result of our paper.

Proof of Theorem 1.1 Together with Lemma 2.4 and Lemma 3.1(1),
$\kappa_{4}(BP_{n})\leq\delta(BP_{n})-1=n-1$ for $n\geq 2$. We shall prove the
reverse inequality by induction on $n$. Firstly, $\kappa_{4}(BP_{2})\geq 1$
since $BP_{2}$ is connected. Now suppose that $n\geq 3$ and the result holds
for any integer $m<n$, i.e., $\kappa_{4}(BP_{m})\geq m-1$. Let
$S=\\{x,y,z,w\\}$ be any 4-subset of $V(BP_{n})$. The following cases are
distinguished.

Case 1. There exists an integer $i\in[[n]]$ such that $S\subseteq V(G^{i})$.

W.l.o.g., we may assume that $\\{x,y,z,w\\}\subseteq V(G^{1})$. By induction
hypothesis, there exist ($n-2$) IDSTs $T_{1},\cdots,T_{n-2}$ in $G^{1}$ since
$G^{1}$ is isomorphic to $BP_{n-1}$. Recall that $\widehat{x}$, $\widehat{y}$,
$\widehat{z}$ and $\widehat{w}$ are out-neighbours of $x,y,z$ and $w$,
respectively. There is a
$\\{\widehat{x},\widehat{y},\widehat{z},\widehat{w}\\}$-tree
$\widehat{T}_{n-1}$ in $BP_{n}\setminus V(G^{1})$ since $BP_{n}\setminus
V(G^{1})$ is connected. Let

$T_{n-1}=\widehat{T}_{n-1}\cup\\{x\widehat{x},y\widehat{y},z\widehat{z},w\widehat{w}\\}.$

Then $T_{1},\cdots,T_{n-2},T_{n-1}$ are ($n-1$) IDSTs in $BP_{n}$.

Case 2. There exists an integer $i\in[[n]]$ such that $|S\cap V(G^{i})|=3$.

By Lemma 4.1, ($n-1$) IDSTs can be obtained in $BP_{n}$.

Case 3. There exist different integers $\\{i,j\\}\subseteq[[n]]$ such that
$|S\cap V(G^{i})|=2$ and $|S\cap V(G^{j})|=2$.

According to Lemma 5.1, ($n-1$) IDSTs can be obtained in $BP_{n}$.

Case 4. There are different integers $i,j$ and $l$ in $[[n]]$ such that
$|S\cap V(G^{i})|=2$ and $|S\cap V(G^{j})|=|S\cap V(G^{l})|=1$.

Based on Lemma 5.2, there are ($n-1$) IDSTs in $BP_{n}$.

Case 5. For any integer $i\in[[n]]$, $|S\cap V(G^{i})|\leq 1$.

By Lemma 6.1, ($n-1$) IDSTs can be obtained in $BP_{n}$.

In all, there are ($n-1$) IDSTs for any 4-subset $S\subseteq V(BP_{n})$.
Therefore, $\kappa_{4}(BP_{n})\geq n-1$ for $n\geq 2$. The proof is completed.
$\Box$

##  8 Conclusion

The generalized $k$-connectivity is a natural generalization of the classical
connectivity and can serve for measuring the capability of a network $G$ to
connect any $k$ vertices in $G$. In this paper, we focused on the generalized
4-connectivity of the burnt pancake graph $BP_{n}$. By Lemma 2.4, the
generalized 4-connectivity of an $n$-regular graph is no more than ($n-1$).
Thus, our result illustrated that the burnt pancake graph $BP_{n}$ has a best
possible fault-tolerance when the generalized 4-connectivity is applied as the
fault-tolerance index. Moreover, $\kappa_{3}(BP_{n})=n-1$ can be derived
directly by Lemma 2.5 and Theorem 1.1. This result was also investigated in
[23].

## References

  * [1] J.A.Bondy, U.S.R.Murty, Graph theory, Springer, New York, 2007
  * [2] G.Chartrand, S.F.Kapoor, L.Lesniak, D.R.Lick, Generalized connectivity in graphs, Bombay Math., 2 (1984) 1-6
  * [3] G. Chartrand, F.Okamoto, P. Zhang, Rainbow trees in graphs and generalized connectivity, Networks, 55 (4) (2010) 360-367
  * [4] D.Cheng, The generalized 4-connectivity of locally twisted cubes, J. of Appl. Math. and Comput., 69 (2023) 3095-3111
  * [5] C.Chin, T.H.Weng, L.H.Hsu, S.C.Chiou, The spanning connectivity of the burnt pancake graphs, IEICE Trans. Inform. Syst., 92 (3) (2009) 389-400
  * [6] P.E.C.Compeau, Girth of pancake graphs, Discret. Appl. Math., 159 (2011) 1641-1645
  * [7] W.H.Gates, C.H.Papadimitriou, Bounds for sorting by prefix reversal, Discret. Math., 27 (1979) 47-49
  * [8] Y.Lai, D.Yu, Mutually independent Hamiltonian cycle of burnt pancake graphs, in: The 27th Workshop on Combinatorial Mathematics and Computation Theory, (2011) 134-140
  * [9] S.Li, Some topics on generalized connectivity of graphs (Ph.D. thesis), Nankai University, (2012)
  * [10] S.Li, X.Li, Note on the hardness of generalized connectivity, J. Comb. Optim., 24 (2012) 389-396
  * [11] S.Li, W.Li, X.Li, The generalized connectivity of complete bipartite graphs, Ars Combin., 104 (2012) 65-79
  * [12] H.Li, X.Li, Y.Mao, Y.Sun, Note on the generalized connectivity, Ars Combin., 114 (2014) 193-202
  * [13] H.Li, X.Li, Y.Sun, The generalized 3-connectivity of Cartesian product graphs, Discret. Math. Theor. Comput. Sci., 14 (1) (2012) 43-54
  * [14] S.Li, X.Li, W.Zhou, Sharp bounds for the generalized connectivity $\kappa_{3}(G)$, Discret. Math., 310 (2010) 2147-2163
  * [15] C.Li, S.Lin, S.Li, The 4-set tree connectivity of ($n,k$)-star networks, Theoret. Comput. Sci., 844 (2020) 81-86
  * [16] H.Li, Y.Ma, W.Yang, Y.Wang, The generalized 3-connectivity of graph products, Appl. Math. Comput., 295 (2017) 77-83
  * [17] S.Li, Y.Shi, J.Tu, The generalized 3-connectivity of Cayley graphs on symmetric groups generated by trees and cycles, Graphs and Combin., 33 (2017) 1195-1209
  * [18] S.Li, J.Tu, C.Yu, The generalized 3-connectivity of star graphs and bubble-sort graphs, Appl. Math. Comput., 274 (2016) 41-46
  * [19] S.Lin, Q.Zhang, The generalized 4-connectivity of hypercubes, Discret. Appl. Math., 220 (2017) 60-67
  * [20] S.Song, X.Li, S.Zhou, M.Chen, Fault tolerance and diagnosability of burnt pancake networks under the comparison model, Theoret. Comput. Sci., 582 (2015) 48-59
  * [21] J.Wang, The generalized 3-connectivity of two kinds of regular networks, Theoret. Comput. Sci., 893 (2021) 183-190
  * [22] J.Wang, F.Li, The generalized 3-connectvity of the folded hypercube $FQ_{n}$, The Comput. Journal, online (2022) https://doi.org/10.1093/comjnl/bxac137
  * [23] J.Wang, Z.Zhang, Y.Huang, The generalized 3-connectivity of burnt pancake graphs and godan graphs, AKCE International J. of Graphs and Combin., 20 (2023) 98-103
  * [24] C.Wei, R.Hao, J.Chang, The reliability analysis based on the generalized connectivity in balanced hypercubes, Discret. Appl. Math., 292 (2021) 19-32
  * [25] H.Whitney, Congruent graphs and connectivity of graphs, J. Amer. Math. Soc., 54 (1932) 150-168
  * [26] S.Zhao, J.Chang, Reliability assessment of the divide-and-swap cube in terms of generalized connectivity, Theoret. Comput. Sci., 943 (2023) 1-15
  * [27] S.Zhao, J.Chang, H.Li, The generalized 4-connectivity of pancake graphs, Discret. Appl. Math., 327 (2023) 77-86
  * [28] S.Zhao, R.Hao, The generalized 4-connectivity of exchanged hypercubes, Appl. Math. and Comput., 347 (2019) 342-353
  * [29] S.Zhao, R.Hao, The generalized three-connectivity of two kinds of Cayley graphs, The Comput. Journal, 62 (2019) 144-149
  * [30] S.Zhao, R.Hao, E.Cheng, Two kinds of generalized connectivity of dual cubes, Discret. Appl. Math., 257 (2019) 306-316
  * [31] S.Zhao, R.Hao, The generalized connectivity of bubble-sort star graphs, International J. Foundations of Comput. Sci., 30 (2019) 793-809
  * [32] S.Zhao, R.Hao, The generalized connectivity of alternating group graphs and $(n,k)$-star graphs, Discret. Appl. Math., 251 (2018) 310-321
  * [33] S.Zhao, R.Hao, S.Peng, Reliability assessment of some regular networks, The Comput. Journal, 64 (2021) 1-6
  * [34] S.Zhao, R.Hao, J.Wu, The generalized 4-connectivity of hierarchical cubic networks. Discret. Appl. Math., 289 (2021) 194-206