ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 23 (2023) #P3.04
https://doi.org/10.26493/1855-3974.2913.35e
(Also available at http://amc-journal.eu)
Component (edge) connectivity of
pancake graphs*
Xiaohui Hua † , Lulu Yang
School of Mathematics and Information Science, Henan Normal University, Xinxiang,
Henan 453007, P. R. China
Received 25 June 2022, accepted 17 November 2022, published online 17 January 2023
Abstract
The l-component (edge) connectivity of a graph G, denoted by cκl(G) (cλl(G)), is
the minimum number of vertices (edges) whose removal from G results in a disconnected
graph with at least l components. The pancake graph Pn is a popular underlying topology
for distributed systems. In the paper, we determine the cκl(Pn) and cλl(Pn) for 3 ≤ l ≤ 5.
Keywords: Component connectivity, component edge connectivity, pancake graphs, fault tolerance.
Math. Subj. Class. (2020): 05C40, 05C75
1 Introduction
Multiprocessor systems are always built according to a graph which is called its intercon-
nection network (network, for short). In a network, vertices correspond to processors, and
edges correspond to communicating links between pairs of vertices. Since failures of pro-
cessors and links are inevitable in multiprocessor systems, fault tolerance is an important
issue in interconnection networks. Fault tolerance of interconnection networks becomes
an essential problem and has been widely studied, such as, structure connectivity and sub-
structure connectivity of hypercubes [20], extra connectivity of bubble sort star graphs [10],
g-extra conditional diagnosability of hierarchical cubic networks [21], g-good-neighbor
connectivity of graphs [25], conditional connectivity of Cayley graphs generated by uni-
cyclic graphs [26].
Given a connected graph G = (V,E), where V is the set of processors and E is the
set of communication links between processors. The connectivity κ(G) of a graph G is
the minimum number of vertices of G, if any, whose deletion disconnect G. The edge
*The authors are grateful to anonymous referees for helpful remarks and suggestions.
†Corresponding author.
E-mail addresses: xhhua@htu.edu.cn (Xiaohui Hua), yllyanglulu@126.com (Lulu Yang)
cb This work is licensed under https://creativecommons.org/licenses/by/4.0/
2 Ars Math. Contemp. 23 (2023) #P3.04
connectivity λ(G) of a graph G is the minimum number of edges of G, if any, whose
deletion disconnect G. The g-extra connectivity of G, denoted by κg(G), is the minimum
number of vertices whose removal separates G such that each component of the remaining
graph has at least g + 1 vertices.
The classic parameter is the connectivity κ(G) and edge connectivity λ(G). In general,
the larger κ(G) or λ(G) is, the more stable the network is. The l-component connectivity
of a graph was first introduced by Chartrand [8] and Sampathkumar [22], independently.
Note that cκ2(G) = κ(G) and cλ2(G) = λ(G) for any graph if it is not a complete
graph. Therefore, the l-component (edge) connectivity can be regarded as a generalization
of the classical (edge) connectivity. The two parameters have been investigated in several
interconnection networks. See for example [3, 7, 12, 16, 23, 27, 28, 29]. Recently, the
relationship between extra connectivity and component connectivity of general networks
has been investigated by Li et al. [14], while the relationship between extra edge connec-
tivity and component edge connectivity of regular networks has been suggested by Hao et
al. [15] and Guo et al. [13], independently.
The pancake graph, denoted by Pn, is one of alternative interconnection networks for
multiprocessor systems, and it poses some attractive topological properties, such as (n −
1)-regular, node-symmetric, bipartite and recursive [1]. The pancake graph has drawn
considerable attention, such as, structure connectivity and substructure connectivity [6],
super connectivity [19] and neighbor connectivity [9, 24] had been considered. For more
examples, see [1, 5, 11, 17, 18, 30] and references therein.
The rest of the paper is organized as follows. Section 2 formally gives the definition of
pancake graphs. In addition, we introduce some preliminary results. Section 3 determines
the l-component connectivity of Pn for l = 3, 4, 5. Section 4 determines the l-component
edge connectivity of Pn for l = 3, 4, 5. Concluding remarks are covered in Section 5.
2 Preliminaries
In this paper, graph-theoretical terminology and notation not defined here mostly follow
[2].
For any two graphs G1 and G2, G1 ∩ G2 = (V (G1) ∩ V (G2), E(G1) ∩ E(G2)).
For any sets A and B, A − B = {x : x ∈ A but x /∈ B} and we sometimes write
A − B as A \ B if B ⊆ A. For X,Y ⊆ V (G), [X,Y ] represents the edge set of G in
which one end is in X and the other is in Y . The distance of two vertices u and v in a
graph G, denote by disG(u, v), is the length of a shortest path between u and v in G. Set
NG(u) = {v : disG(u, v) = 1}, and set NG(U) =
⋃
u∈U NG(u) − U . For any vertex v,
denote by E(v) the edges incident to v. A k-cycle, denoted by Ck, is a cycle on k vertices,
and a k-path u1u2...uk, is a path on k vertices. Let ⟨n⟩ = {1, 2, · · · , n}.
Definition 2.1 ([1]). The n-dimensional pancake graph is denoted by Pn. The vertex set
V (Pn) = {u = u1u2 · · ·un|ui ∈ ⟨n⟩, ui ̸= uj for i ̸= j}, the edge set E(Pn) = {uv|u =
u1u2 · · ·uk · · ·un, v = uk = ukuk−1 · · ·u2u1uk+1 · · ·un−1un and 2 ≤ k ≤ n}, where
uk denotes the unique k-neighbour of u, the edge uuk is called k-edge.
Clearly, Pn consists of (n− 1) kinds of edges. The pancake graphs P2, P3 and P4 are
shown in Figure 1. The pancake graphs are Cayley graphs with having the hierarchical (re-
cursive) structure. The removal of all n-edges from Pn results in n connected components
P 1n , P
2
n , · · · , Pnn , where P in is the subgraph of Pn induced by {u = u1u2 · · ·un ∈ V (Pn) :
X. Hua and L. Yang: Component (edge) connectivity of pancake graphs 3
Figure 1: The pancake graphs P2, P3 and P4.
un = i}. Clearly, P in is isomorphic to the (n − 1)-dimensional pancake graph Pn−1 [17].
We call P in a sub-pancake of Pn. For any vertex u ∈ V (P in), just one vertex in N(u) is not
in V (P in), we define this vertex to be out-neighbor of u. For i ̸= j ∈ ⟨n⟩, an edge is called
a cross-edge if its two terminal vertices are in P in and P
j
n, respectively.
Lemma 2.2 ([1, 5, 17, 18]). An n-dimensional pancake graph Pn has the following com-
binatorial properties.
(1) Pn has n! vertices, (n− 1)n!/2 edges, (n− 1)-regular.
(2) The girth of Pn is 6 for n ≥ 3. Let the 6-cycle be presented as u1u2u3u4u5u6. Then
u1u2, u3u4, u5u6 are 2-edges and u2u3, u4u5, u1u6 are 3-edges.
(3) For any i ̸= j, the number of cross edges between P in and P jn is (n− 2)!.
Remark 2.3. One and the same path of length 2 cannot be contained in two 6-cycles.
Lemma 2.4 ([30]). Let F be a set of faulty vertices in Pn with |F | ≤ 2n− 4 for n ≥ 5. If
Pn −F is disconnected, then it has exactly two components, one of which is a singleton or
a single edge.
In [4], Chen and Tan proposed the family of interconnection networks SPn. It is obvi-
ously that Pn is one of the network of SPn.
Lemma 2.5 ([11]). Let F be a set of faulty vertices in Pn with |F | ≤ 2n− 5 for n ≥ 3. If
Pn − F is disconnected, then it has exactly two components, one of which is a singleton.
Lemma 2.6 ([11, 30]). Let F be a set of faulty vertices in Pn with |F | ≤ 3n−8 for n ≥ 5.
If Pn − F is disconnected, then it either has two components, one of which is a singleton
or a single edge, or has three components, two of which are singletons.
Lemma 2.7 ([11]). Let F be a set of faulty vertices in Pn with |F | ≤ 4n − 11 for n ≥ 6.
If Pn − F is disconnected, then Pn − F satisfies one of the following conditions:
(1) Pn−F has two components, one of which is a singleton or a single edge or a 3-path;
4 Ars Math. Contemp. 23 (2023) #P3.04
(2) Pn − F has three components, two of which are singletons;
(3) Pn−F has three components, two of which are a singleton and an edge, respectively;
(4) Pn − F has four components, three of which are singletons.
Lemma 2.8 ([4, 11]). κ1(Pn) = 2n − 4 for n ≥ 3, κ2(Pn) = 3n − 7 for n ≥ 5 and
κ3(Pn) = 4n− 10 for n ≥ 6.
Hereafter, we suppose that F is a vertex cut or an edge cut in Pn. For each i ∈ ⟨n⟩, let
Fi = F ∩ V (P in) or Fi = F ∩ E(P in), and fi = |Fi|. Let I = {i ∈ ⟨n⟩|fi ≥ n − 2},
P In =
⋃
i∈I P
i
n, FI =
⋃
i∈I Fi, and let J = ⟨n⟩ \ I , P Jn =
⋃
j∈J P
j
n, FJ =
⋃
j∈I fj . Also,
we Let H be the union of smaller components of Pn − F and let c(H) be the number of
components of H .
3 The component connectivity of Pn
Lemma 3.1. Let S be an independent set of V (Pn) for n ≥ 4. Then the following asser-
tions hold.
(1) If |S| = 2, then |N(S)| ≥ 2n− 3.
(2) If |S| = 3, then |N(S)| ≥ 3n− 6.
(3) If |S| = 4, then |N(S)| ≥ 4n− 8.
Proof. For (1), let S = {v1, v2}. By Lemma 2.2, Pn contains no 4-cycle. Thus, v1 and v2
have at most one common neighbor, and |N(S)| = |N(v1)|+|N(v2)|−|N(v1)∩N(v2)| ≥
2n− 3.
For (2), let S = {v1, v2, v3}. By Lemma 2.2, Pn contains 6-cycle, there exists at
most three common neighbors among these three singletons. Thus, we have |N(S)| ≥∑3
i=1 |N(vi)| − 3 ≥ 3n− 6.
For (3), let S = {v1, v2, v3, v4}. Since Pn contains 8-cycle, and in order to make
these four singletons contain as many common vertices as possible, we may assume that
the 8-cycle is presented as v1u1v2u2v3u3v4u4. Then there exists four common neighbors
among these four singletons. If there exists five common neighbors among these four
singletons, then it forms a cycle of length less than 6 or two 6-cycles with common 2-
path, contradicting Lemma 2.2(2) and Remark 2.3, respectively. Thus, we have |N(S)| ≥∑4
i=1 |N(vi)| − 4 ≥ 4n− 8.
The following remark provides instances that attain the bounds for the assertions of
Lemma 3.1.
Remark 3.2. Let x = 123 · · ·n, y = (x2)3, z = (y2)3, w = (y2)n, o = (w2)3. Clearly,
{x, y, z} is an independent set of Pn and {x, y, z} lie on a 6-cycle in the subgraph of Pn,
{x, y, w, o} is an independent set of Pn and {x, y, w, o} lie on a 8-cycle in the subgraph of
Pn. Clearly, if S = {x, y}, then |N(S)| = 2n − 3. Since Pn − F has three components,
we have cκ3(Pn) ≤ 2n − 3. Similarly, if S = {x, y, z}, then |N(S)| = 3n − 6. Since
Pn − F has four components, we have cκ4(Pn) ≤ 3n− 6. Also, if S = {x, y, w, o}, then
|N(S)| = 4n− 8. Since Pn − F has five components, we have cκ5(Pn) ≤ 4n− 8.
Theorem 3.3. For n ≥ 3, cκ3(Pn) = 2n− 3.
X. Hua and L. Yang: Component (edge) connectivity of pancake graphs 5
Proof. It is true if n = 3. From Remark 3.2, we obtain the upper bound cκ3(Pn) ≤ 2n− 3
for n ≥ 4. It suffices to show cκ3(Pn) ≥ 2n − 3. Suppose on the contrary that there is a
vertex cut F with |F | ≤ 2n− 4, and Pn − F has at least three components.
We first consider that n = 4. Since |F | ≤ 4, it is clear that |I| ≤ 2. If |I| = 1, let
I = {i}, then fi ∈ {2, 3, 4}. If |I| = 2, let I = {i, j}, then fi = fj = 2. No matter
which case, it’s not hard to prove that P4−F has at most two components, a contradiction.
We now consider that n ≥ 5. By Lemma 2.4, Pn − F has exactly two components, a
contradiction.
Thus, cκ3(Pn) ≥ 2n− 3.
Next, we give a lemma which is used by Theorem 3.5 and 3.6.
Lemma 3.4. For n ≥ 5, if |I| ≤ 3, then P Jn − FJ is connected.
Proof. By the definition of J , we have |J | = n − |I| ≥ n − 3 ≥ 2 for n ≥ 5 and
fj ≤ n − 3 for j ∈ J . Since each subgraph P jn is isomorphic to Pn−1, by Lemma 2.2,
we have κ(P jn) = n − 2. Thus, for each j ∈ J , P jn − Fj is connected. For distinct
j, k ∈ J , by Lemma 2.2, the number of cross edges between P jn and P kn is (n− 2)!, since
(n − 2)! > 2(n − 3) for n ≥ 5, we have P jn − Fj is connected to P kn − Fk. Therefore,
P Jn − FJ is connected.
Theorem 3.5. For n ≥ 4, cκ4(Pn) = 3n− 6.
Proof. Remark 3.2 acquires the upper bound cκ4(Pn) ≤ 3n − 6 for n ≥ 4. It suffices to
show cκ4(Pn) ≥ 3n − 6. Suppose that there is a vertex cut F with |F | ≤ 3n − 7, and
Pn − F has at least four components.
We first consider that n = 4. By Theorem 3.3, cκ3(P4) = 5 and |F | ≤ 3n− 7 = 5, we
have know Pn − F has at most three components, a contradiction.
Next, Let n ≥ 5. Lemma 2.6 shows that the removal of a vertex cut with no more that
3n − 8 vertices in Pn results in a disconnected graph with at most three components, a
contradiction. To complete the proof, we need to show result holds when |F | = 3n − 7.
Partition Pn into n disjoint copies P 1n , P
2
n , · · · , Pnn of Pn−1 along dimension n. Recall that
I = {i ∈ ⟨n⟩ : fi ≥ n − 2}. Since |F | = 3n − 7, it is clear that |I| ≤ 2. By Lemma 3.4,
P Jn − FJ is connected. If |I| = 0, then Pn − F = P Jn − FJ is connected, a contradiction.
Consider the following cases.
Case 1: |I| = 1. Let I = {i}.
Case 1.1: n− 2 ≤ fi ≤ 3(n− 1)− 8.
Since each subgraph P in is isomorphic to Pn−1, by Lemma 2.6, P
i
n − Fi has at most
three components, and all small components contain at most two vertices in total. Since
(n−1)!−2 > 3n−7 for n ≥ 5, the large component of P in−Fi is connected to P Jn −FJ .
This implies that |V (H)| ≤ 2. It is clear that c(H) ≤ |V (H)| ≤ 2, a contradiction.
Case 1.2: 3n− 10 ≤ fi ≤ 3n− 7.
In this case, we have FJ = |F | − fi ≤ (3n− 7)− (3n− 10) = 3. Since every vertex
of H has exactly one out-neighbor, we have |V (H)| ≤ 3. If |V (H)| = 3, then c(H) ≤ 2.
Otherwise, c(H) = 3 and it implies that H is a set of three singletons. By Lemma 3.1, we
have |NPn(V (H))| ≥ 3n− 6 > 3n− 7 = |F |, a contradiction. If |V (H)| ≤ 2, it is clear
that c(H) ≤ |V (H)| ≤ 2, a contradiction.
Case 2: |I| = 2.
6 Ars Math. Contemp. 23 (2023) #P3.04
Let I = {i, j}. Without loss of generality, assume fi ≤ fj . Since |F | = 3n − 7,
we have n − 2 ≤ fi ≤ fj ≤ (3n − 7) − (n − 2) = 2n − 5. If fi = 2n − 5, then
fi + fj = 2(2n− 5) = 4n− 10 > 3n− 7 for n ≥ 5. Thus, it requires that fi ≤ 2n− 6.
Case 2.1: n− 2 ≤ fi ≤ fj ≤ 2n− 6.
For l ∈ {i, j}, if P ln − Fl is disconnected, by Lemma 2.4, P ln − Fl has at most two
components, one of which is a singleton or an edge. Since (n−1)!− (n−2)!−2 > 3n−7
for n ≥ 5 and l ∈ {i, j}, then the large component of P ln − Fl is connected to P Jn − FJ . It
implies that c(H) ≤ 2, a contradiction.
Case 2.2: fj = 2n− 5, and fi = n− 2.
Since |F | = 3n − 7, we have FJ = |F | − fi − fj = 0. Thus, at most two vertices in
P in ∪ P jn − (Fi ∪ Fj) cannot connect with P Jn − FJ in Pn − F , and the two vertices form
an edge. Thus, c(H) ≤ 1, a contradiction.
Theorem 3.6. For n ≥ 6, cκ5(Pn) = 4n− 8.
Proof. Remark 3.2 acquires the upper bound cκ5(Pn) ≤ 4n − 8. It suffices to show
cκ5(Pn) ≥ 4n− 8.
Suppose that there is a vertex cut F with |F | ≤ 4n − 9, and Pn − F has at least
five components. Lemma 2.7 shows that the removal of a vertex cut with no more that
4n − 11 vertices in Pn results in a disconnected graph with at most four components, a
contradiction. To complete the proof, we need to show result holds when 4n− 10 ≤ |F | ≤
4n − 9. Partition Pn into n disjoint copies P 1n , P 2n , · · · , Pnn of Pn−1 along dimension n.
Recall that I = {i ∈ ⟨n⟩ : fi ≥ n − 2}. Since |F | ≤ 4n − 9, it is clear that |I| ≤ 3. By
Lemma 3.4, P Jn − FJ is connected. If |I| = 0, then Pn − F = P Jn − FJ is connected, a
contradiction.
Consider the following cases.
Case 1: |I| = 1. Let I = {i}.
Case 1.1: n− 2 ≤ fi ≤ 4(n− 1)− 11.
Since each subgraph P in is isomorphic to Pn−1, by Lemma 2.7, P
i
n − Fi has at most
four components, and all small components contain at most three vertices in total. Since
(n−1)!−3 > 4n−9 for n ≥ 6, the large component of P in−Fi is connected to P Jn −FJ .
This implies that |V (H)| ≤ 3. It is clear that c(H) ≤ |V (H)| ≤ 3, a contradiction.
Case 1.2: 4n− 14 ≤ fi ≤ 4n− 9.
In this case, we have FJ = |F | − fi ≤ (4n− 9)− (4n− 14) = 5. Since every vertex
of H has exactly one out-neighbor, we have |V (H)| ≤ 5. If |V (H)| = 5, then c(H) ≤ 3.
Otherwise, c(H) ≥ 4 and it implies that H contains five singletons or three singletons
together with an edge. In the former case, let H = H0 ∪ {x}, where H0 is a set of four
singletons and x is a singleton. By Lemma 3.1(3), we have |NPn(V (H0))| ≥ 4n − 8.
Clearly, |NPn(V (H))| = |NPn(V (H0))|+ |NPn(x)| − |NPn(V (H)) ∩NPn(x)| ≥ 4n−
8 + (n − 1) − 4 = 5n − 13 > 4n − 9 ≥ |F | for n ≥ 6, a contradiction. In the latter
case, let H = H0 ∪ {u, v}, where H0 is a set of three singletons and uv is an edge.
Then, we have |NPn(V (H0))| ≥ 3n− 6 by Lemma 3.1(2) and |NPn({u, v})| = 2n− 4 by
Lemma 2.8. Also, the girth of Pn is 6 and it follows that |NPn(V (H))∩NPn({u, v})| ≤ 3.
Thus |NPn(V (H))| = |NPn(V (H0))|+ |NPn({u, v})| − |NPn(V (H))∩NPn({u, v})| ≥
3n − 6 + (2n − 4) − 3 = 5n − 13 > 4n − 9 ≥ |F | for n ≥ 6, a contradiction. If
|V (H)| = 4, then c(H) ≤ 3. Otherwise, H contains four singletons. By Lemma 3.1(3),
X. Hua and L. Yang: Component (edge) connectivity of pancake graphs 7
we have |NPn(V (H))| ≥ 4n − 8 > 4n − 9 ≥ |F |, a contradiction. Also, if |V (H)| ≤ 3,
it is clear that c(H) ≤ |V (H)| ≤ 3, a contradiction.
Case 2: |I| = 2.
Let I = {i, j}. Without loss of generality, assume fi ≤ fj . Since |F | ≤ 4n − 9,
we have n − 2 ≤ fi ≤ fj ≤ (4n − 9) − (n − 2) = 3n − 7. If fi ≥ 3n − 10, then
fi + fj ≥ 2(3n− 10) = 6n− 20 > 4n− 9 for n ≥ 6. Thus, it requires that fi ≤ 3n− 11.
Case 2.1: n− 2 ≤ fi ≤ fj ≤ 3n− 11.
For each l ∈ {i, j}, if P ln − Fl is disconnected, by Lemma 2.6, P ln − Fl has at most
three components and all smaller components contain at most two vertices in total. Since
(n− 1)!− (n− 2)!− 2 > 4n− 9 for n ≥ 6, the large component of P ln − Fl is connected
to P Jn − FJ . Thus, |V (H)| ≤ 2|I| = 4. If |V (H)| = 4, then c(H) ≤ 3. Otherwise, H
contains four singletons. By Lemma 3.1(3), we have |NPn(V (H))| ≥ 4n − 8 > 4n −
9 ≥ |F |, a contradiction. Also, if |V (H)| ≤ 3, it is clear that c(H) ≤ |V (H)| ≤ 3, a
contradiction.
Case 2.2: 3n− 10 ≤ fj ≤ 3n− 7, and n− 2 ≤ fi ≤ 4n− 9− (3n− 10) = n+ 1.
P in − Fi has at most two components, one of which is a singleton. If fj = 3n − 10,
by Theorem 3.5, P jn − Fj has at most three components. Then FJ = |F | − fi − fj ≤
4n− 9− (n− 2)− (3n− 10) = 3. If 3n− 9 ≤ fj ≤ 3n− 7, then FJ = |F | − fi − fj ≤
4n− 9− (n− 2)− (3n− 9) = 2. No matter which case, c(H) ≤ 3, a contradiction.
Case 3: |I| = 3.
Let I = {i, j, k}. Without loss of generality, assume fi ≤ fj ≤ fk. Since |F | ≤ 4n−9,
we have n − 2 ≤ fi ≤ fj ≤ fk ≤ (4n − 9) − 2(n − 2) = 2n − 5. If fi ≥ 2n − 6, then
fi+fj+fk ≥ 3(2n−6) = 6n−18 > 4n−9 for n ≥ 6. Thus, it requires that fi ≤ 2n−7.
If fj ≥ 2n− 6, then fi + fj + fk ≥ n− 2 + 2(2n− 6) = 5n− 14 > 4n− 9 for n ≥ 6.
Thus, it requires that fj ≤ 2n− 7.
Case 3.1: n− 2 ≤ fi ≤ fj ≤ fk ≤ 2n− 7.
For each l ∈ {i, j, k}, if P ln − Fl is disconnected, by Lemma 2.5, P ln − Fl has at most
two components, one of which is a singleton. Since (n− 1)!− 2(n− 2)!− 1 > 4n− 9 for
n ≥ 6, the large component of P ln−Fl is connected to P Jn −FJ . Thus, |V (H)| ≤ 3|I| = 3.
It is clear that c(H) ≤ |V (H)| ≤ 3, a contradiction.
Case 3.2: n− 2 ≤ fi ≤ fj ≤ 2n− 7 < fk ≤ 2n− 5.
For each l ∈ {i, j}, if P ln − Fl is disconnected, by Lemma 2.5, P ln − Fl has at
most two components, one of which is a singleton. By a similar argument as Case 3.1,
the large component of P ln − Fl is connected to P Jn − FJ . Since |fk| ≤ 2n − 5 ≤
3(n−1)−8 for n ≥ 6, by Lemma 2.6, either P kn −Fk is connected or P kn −Fk has at most
three components and all smaller components contain at most two vertices in total. Since
(n − 1)! − 2(n − 2)! − 2 > 4n − 9 ≥ |F | for n ≥ 6, the large component of P kn − Fk is
connected to P Jn − FJ . Thus, |V (H)| ≤ 4. Then, an argument similar to Case 2.1 shows
that c(H) ≤ 3, a contradiction.
4 The edge component connectivity of Pn
Theorem 4.1. For n ≥ 3, cλ3(Pn) = 2n− 3.
Proof. Take an edge e = xy and F = E(x)∪E(y). Then |F | = 2n−3 and Pn−F has at
least three components. Hence cλ3(Pn) ≤ 2n− 3. It suffices to show cλ3(Pn) ≥ 2n− 3.
8 Ars Math. Contemp. 23 (2023) #P3.04
We consider an inductive proof as follows. The statement of theorem holds for n = 3.
We assume that the result holds for Pn−1, and prove that it also holds for Pn, where n ≥ 4.
Suppose that there is an edge set F with |F | ≤ 2n − 4, and Pn − F has at least three
components. Consider n disjoint copies P 1n , P
2
n , · · · , Pnn . Since I = {i ∈ ⟨n⟩ : fi ≥
n− 2}, and |F | ≤ 2n− 4, it is clear that |I| ≤ 2.
Consider the following cases.
Case 1: |I| = 0.
Each P in − Fi is connected for i ∈ ⟨n⟩. For distinct i, j ∈ ⟨n⟩, by Lemma 2.2, the
number of cross edges between P in and P
j
n is (n − 2)!. Since (2n − 4) < 3(n − 2)! for
n ≥ 4, there are at most two [P in, P jn]’s which are contained in F for distinct i, j ∈ ⟨n⟩.
Thus Pn − F is connected, a contradiction.
Case 2: |I| = 1. Let I = {i}.
Case 2.1: n− 2 ≤ fi ≤ 2(n− 1)− 4.
If each P in − Fi is connected for i ∈ ⟨n⟩, since (2n − 4) − (n − 2) < 2(n − 2)! for
n ≥ 4, then there is at most one [P in, P jn] which is contained in F for distinct i, j ∈ ⟨n⟩.
Thus, Pn − F is connected, a contradiction. Hence, there exists i such that P in − Fi is not
connected. By the inductive hypothesis, P in − Fi has at most two components.
Since (2n− 4)− (n− 2) < 2(n− 2)! for n ≥ 4, there is at most one [P jn, P kn ] which
is contained in F for distinct j, k ∈ ⟨n⟩ \ {i}. Thus P Jn − FJ is connected. Furthermore,
|[P in, P Jn −FJ ]| = (n−1)! > 2n−4−(n−2) for n ≥ 4. At least one component of P in−Fi
is connected to P Jn − FJ . Hence Pn − F has at most two components, a contradiction.
Case 2.2: 2n− 5 ≤ fi ≤ 2n− 4.
In this case, we have |F |−fi ≤ (2n−4)− (2n−5) = 1. Then P Jn −FJ is connected.
Note that at most one vertex of P in −Fi is disconnected to P Jn −FJ . Hence Pn −F has at
most two components, a contradiction.
Case 3: |I| = 2.
Let I = {i, j}. Then fi = fj = n − 2 and |F | − fi − fj = 0. Thus P ln − Fl has
at most two components for any l ∈ {i, j} and P Jn − FJ is connected. And so either any
component of P ln − Fl is connected to P Jn − FJ or two singletons are connected and the
other component of P ln − Fl is connected to P Jn − FJ if both P in − Fi and P jn − Fj have a
singleton, respectively. Thus Pn − F has at most two components, a contradiction.
Theorem 4.2. For n ≥ 3, cλ4(Pn) = 3n− 5.
Proof. Take a 3-path xyz and F = E(x)∪E(y)∪E(z). Then |F | = 3n−5 and Pn−F has
at least four components. Hence cλ4(Pn) ≤ 3n−5. It suffices to show cλ4(Pn) ≥ 3n−5.
We consider an inductive proof as follows. The statement of theorem holds for n = 3.
We assume that the result holds for Pn−1, and prove that it also holds for Pn, where n ≥ 4.
Suppose that there is an edge set F with |F | ≤ 3n − 6, and Pn − F has at least four
components. Consider n disjoint copies P 1n , P
2
n , · · · , Pnn . Since I = {i ∈ ⟨n⟩ : fi ≥
n− 2}, and |F | ≤ 3n− 6, it is clear that |I| ≤ 3.
Consider the following cases.
Case 1: |I| = 0.
Similar to the proof of Case 1 of Theorem 4.1, we can show that Pn − F is connected
for n ≥ 5, a contradiction. Consider that n = 4. Since (4−2)! = 2 and |F | ≤ 3n− 6 = 6,
X. Hua and L. Yang: Component (edge) connectivity of pancake graphs 9
there are at most three [P i4, P
j
4 ]’s which are contained in F . Hence P4 −F has at most two
components, a contradiction.
Case 2: |I| = 1. Let I = {i}.
Case 2.1: n− 2 ≤ fi ≤ 3(n− 1)− 6.
Similar to the proof of Case 2.1 of Theorem 4.1, we can show that Pn − F has at most
three components for n ≥ 5, a contradiction. Consider that n = 4. Then 2 ≤ fi ≤ 3. If
fi = 2, then P i4 − Fi has at most two components, and |F | − fi ≤ (3n− 6)− 2 = 4. It is
not hard to prove that P4 −F has at most two components, a contradiction. If fi = 3, then
P i4 − Fi has at most three components, and |F | − fi ≤ (3n− 6)− 3 = 3. It is not hard to
prove that P4 − F has at most three components, a contradiction.
Case 2.2: 3n− 8 ≤ fi ≤ 3n− 6.
In this case, we have |F | − fi ≤ (3n − 6) − (3n − 8) = 2. Furthermore, P Jn − FJ is
connected. Note that at most two vertices of P in −Fi are disconnected to P Jn −FJ . Hence
Pn − F has at most three components, a contradiction.
Case 3: |I| = 2.
Let I = {i, j}. Without loss of generality, assume fi ≤ fj . Then fj ≤ 3n − 6 −
(n− 2) = 2n− 4.
Case 3.1: n− 2 ≤ fj ≤ 2(n− 1)− 4.
In this case, we have n− 2 ≤ fi ≤ fj ≤ 2(n− 1)− 4. By Theorem 4.1, both P in − Fi
and P jn − Fj have at most two components.
Consider that n = 4. Then fi = fj = 2, implying that P l4 − Fl has at most two
components for l ∈ {i, j}, and |F | − fi − fj ≤ (3n − 6) − 2 − 2 = 2. It is not hard to
prove that P4 − F has at most three components, a contradiction.
Consider that n ≥ 5. Since |[P kn , P ln]| = (n − 2)! > 3n − 6 − 2(n − 2) for n ≥ 5
and k, l ∈ ⟨n⟩ \ {i, j}, P Jn −FJ is connected. Furthermore, |[P in, P Jn −FJ ]| = (n− 1)!−
(n− 2)! > 3n− 6− 2(n− 2) for n ≥ 5. At least one component of P in − Fi is connected
to P Jn −FJ . Similarly, at least one component of P jn−Fj is connected to P Jn −FJ . Hence
Pn − F has at most three components, a contradiction.
Case 3.2: fj = 2n− 5.
Then n− 2 ≤ fi ≤ 3n− 6− (2n− 5) = n− 1.
If fi = n − 2, P in − Fi has at most two components. Then |F | − fi − fj ≤ 1, and
so P Jn − FJ is connected. Thus Pn − F has at most three components, a contradiction. If
fi = n− 1, then |F | − fi − fj = 0 and P Jn − FJ is connected. Thus Pn − F has at most
three components, a contradiction.
Case 3.3: fj = 2n− 4.
Then fi = n − 2 and |F | − fi − fj = 0. Thus P in − Fi has at most two components
and P Jn − FJ is connected. Thus Pn − F has at most two components, a contradiction.
Case 4: |I| = 3.
Let I = {i, j, k}. Then fi = fj = fk = n − 2 and |F | − fi − fj − fk = 0. Thus
P ln − Fl has at most two components for any l ∈ {i, j, k}. Thus Pn − F has at most two
components, a contradiction.
Theorem 4.3. For n ≥ 3, cλ5(Pn) = 4n− 7.
Proof. Take a 4-path xyzw and F = E(x) ∪ E(y) ∪ E(z) ∪ E(w). Then |F | = 4n − 7
and Pn − F has at least five components. Hence cλ5(Pn) ≤ 4n − 7. It suffices to show
cλ5(Pn) ≥ 4n− 7.
10 Ars Math. Contemp. 23 (2023) #P3.04
We consider an inductive proof as follows. The statement of theorem holds for n = 3.
We assume that the result holds for Pn−1, and prove that it also holds for Pn, where n ≥ 4.
Suppose that there is an edge set F with |F | ≤ 4n − 8, and Pn − F has at least five
components. Consider n disjoint copies P 1n , P
2
n , · · · , Pnn . Since I = {i ∈ ⟨n⟩ : fi ≥
n− 2}, and |F | ≤ 4n− 8, it is clear that |I| ≤ 4.
Consider the following cases.
Case 1: |I| = 0.
Similar to the proof of Case 1 of Theorem 4.2, we can show that Pn − F is connected
for n ≥ 5 and P4 − F has at most two components, a contradiction.
Case 2: |I| = 1. Let I = {i}.
Case 2.1: n− 2 ≤ fi ≤ 4(n− 1)− 8.
Similar to the proof of Case 2.1 of Theorem 4.1, we can show that Pn − F has at
most three components for n ≥ 5, a contradiction. Consider that n = 4. Then 2 ≤
fi ≤ 4 and (4 − 2)! = 2. If fi = 2, then P i4 − Fi has at most two components, and
|F | − fi ≤ (4n − 8) − 2 = 6. It is not hard to prove that P4 − F has at most three
components, a contradiction. If fi = 3, then P i4 − Fi has at most three components, and
|F | − fi ≤ (4n − 8) − 3 = 5. It is not hard to prove that P4 − F has at most three
components, a contradiction. If fi = 4, then P i4 −Fi has at most four components, three of
which are singletons, and |F | − fi ≤ (4n− 8)− 4 = 4. It is not hard to prove that P4 −F
has at most four components, a contradiction.
Case 2.2: 4n− 11 ≤ fi ≤ 4n− 8.
In this case, we have |F | − fi ≤ (4n − 8) − (4n − 11) = 3. Since 3 < 2(n − 2)!
for n ≥ 4, there is at most one [P jn, P kn ] which is contained in F for j, k ∈ ⟨n⟩ \ {i}, and
so P Jn − FJ is connected. Note that at most three vertices of P in − Fi are disconnected to
P Jn − FJ . Hence Pn − F has at most four components, a contradiction.
Case 3: |I| = 2.
Let I = {i, j}. Without loss of generality, assume fi ≤ fj . Then fj ≤ 4n− 8− (n−
2) = 3n− 6.
Case 3.1: n− 2 ≤ fj ≤ 2(n− 1)− 4.
Similar to the proof of Case 3.1 of Theorem 4.2, we can show that Pn − F has at most
three components, a contradiction.
Case 3.2: 2n− 5 ≤ fj ≤ 3n− 9.
Consider that n = 4. Then fj = 3 and 2 ≤ fi ≤ 3. Then P j4 − Fj has at most three
components. If fi = 2, then P i4 − Fi has at most two components, and |F | − fi − fj ≤
(4n− 8)− 2− 3 = 3. It is not hard to prove that P4 − F has at most four components, a
contradiction. If fi = 3, then P i4 − Fi has at most three components, and |F | − fi − fj ≤
(4n−8)−3−3 = 2. Suppose either P i4−Fi or P
j
4 −Fj contains no singleton, it is not hard
to prove that P4 −F has at most three components, a contradiction. Suppose both P i4 −Fi
and P j4 −Fj contain singletons, then P4−F has at most four components, a contradiction.
Otherwise, P4−F have five components, four of which are singletons. If two singletons of
P l4 are not an edge of P
l
4 for l ∈ {i, j}, then fl ≥ 4, a contradiction. Thus, two singletons
form an edge of P i4 and the other two singletons form an edge of P
j
4 , implying that the four
singletons form a 4-cycle, contradicting Lemma 2.2(2).
X. Hua and L. Yang: Component (edge) connectivity of pancake graphs 11
Consider that n ≥ 5. If fi ≥ 2n − 3, then fi + fj ≥ 2(2n − 3) > 4n − 8 ≥ |F |,
a contradiction. Thus n − 2 ≤ fi ≤ 2n − 4. Note that 2n − 5 ≤ fj ≤ 3n − 9. By
Theorem 4.2, P jn − Fj has at most three components. Since |[P kn , P ln]| = (n − 2)! >
4n− 8− (n− 2)− (2n− 5) for k, l ∈ ⟨n⟩ \ {i, j}, P Jn − FJ is connected. Furthermore,
|[P in, P Jn − FJ ]| = (n − 1)! − (n − 2)! > 4n − 8 − (n − 2) − (2n − 5). At least one
component of P in − Fi is connected to P Jn − FJ . Similarly, at least one component of
P jn − Fj is connected to P Jn − FJ .
If n− 2 ≤ fi ≤ 2n− 6, by Theorem 4.1, P in −Fi has at most two components. Hence
Pn −F has at most four components, a contradiction. If fi = 2n− 5, and assume first that
fj = 2n−5. Then |F |−fi−fj = 4n−8− (2n−5)− (2n−5) = 2. By Theorem 4.1, we
have P ln − Fl has three components for l ∈ {i, j}. Similar to the case of fi = 3 in the first
paragraph of Case 3.2, Pn −F has at most four components, a contradiction. Now assume
that 2n−4 ≤ fj ≤ 2n−3, then |F |−fi−fj ≤ 4n−8−(2n−5)−(2n−4) = 1. It is not
hard to prove that Pn − F has at most three components, a contradiction. If fi = 2n − 4,
then fj = fi = 2n − 4 and |F | − fi − fj = 4n − 8 − 2(2n − 4) = 0. By Theorem 4.2,
P in − Fi has at most three components. Hence Pn − F has at most three components, a
contradiction.
Case 3.3: fj = 3n− 8.
It follows that n − 2 ≤ fi ≤ n. If fi = n − 2, by Theorem 4.1, P in − Fi has at most
two components. Then |F | − fi − fj ≤ 4n − 8 − (3n − 8) − (n − 2) = 2. It is not
hard to prove that Pn − F has at most four components, a contradiction. If fi = n− 1, by
Theorem 4.2, n− 1 < 3(n− 1)− 5 for n ≥ 4, then P in−Fi has at most three components,
and |F | − fi − fj ≤ 4n − 8 − (3n − 8) − (n − 1) = 1. Then Pn − F has at most
four components, a contradiction. If fi = n, then |F | − fi − fj = 0. By Theorem 4.2,
both P in − Fi and P jn − Fj have at most four components. Then Pn − F has at most four
components, a contradiction.
Case 3.4: fj = 3n− 7.
Similar to the proof of Case 3.3 of Theorem 4.3, we can show that Pn − F has at most
three components, a contradiction.
Case 3.5: fj = 3n− 6.
Then fi = n − 2 and |F | − fi − fj = 0. By Theorem 4.1, P in − Fi has at most two
components. Thus Pn − F has at most two components, a contradiction.
Case 4: |I| = 3.
Let I = {i, j, k}. Without loss of generality, assume fi ≤ fj ≤ fk. Then fk ≤
4n − 8 − 2(n − 2) = 2n − 4. Consider n = 4. Then fi = 2, fj = 2, fk = 2, or
fi = 2, fj = 2, fk = 3, or fi = 2, fj = 2, fk = 4, or fi = 2, fj = 3, fk = 3. No matter
which case, it’s not hard to prove that P4−F has at most four components, a contradiction.
Next, we consider n ≥ 5. If fj ≥ 2n − 5, then fi + fj + fk ≥ n − 2 + 2(2n − 5) =
5n− 12 > 4n− 8 ≥ |F | for n ≥ 5, a contradiction. Then fj ≤ 2n− 6.
Case 4.1: n− 2 ≤ fi ≤ fj ≤ fk ≤ 2n− 6.
By Theorem 4.1, P ln − Fl has at most two components for any l ∈ {i, j, k}. Since
|[P xn , P yn ]| = (n− 2)! > 4n− 8− 3(n− 2) for n ≥ 5 and x, y ∈ ⟨n⟩ \ {i, j, k}, P Jn − FJ
is connected. Furthermore, |[P ln, P Jn − FJ ]| = (n− 1)!− 2(n− 2)! > 4n− 8− 3(n− 2)
for n ≥ 5. At least one component of P ln − Fl is connected to P Jn − FJ . Hence Pn − F
has at most four components, a contradiction.
Case 4.2: n− 2 ≤ fi ≤ fj ≤ 2n− 6 < fk ≤ 2n− 4.
12 Ars Math. Contemp. 23 (2023) #P3.04
By Theorem 4.1, P ln − Fl has at most two components for any l ∈ {i, j}, and by
Theorem 4.2, P kn − Fk has at most three components. Since |F | − fi − fj − fk ≤
4n − 8 − 2(n − 2) − (2n − 5) = 1, P Jn − FJ is connected, and at most four vertices
of P in−Fi, P jn−Fj and P kn −Fk are disconnected to P Jn −FJ . If four vertices of P in−Fi,
P jn −Fj and P kn −Fk are disconnected to P Jn −FJ , then two of which forms an edge, and
then Pn −F has at most four components, a contradiction. Otherwise, Pn −F has at most
four components, a contradiction.
Case 5: |I| = 4.
Let I = {i, j, k, p}. Then fi = fj = fk = fp = n−2 and |F |−fi−fj −fk−fp = 0.
Thus P ln − Fl has at most two components for any l ∈ {i, j, k, p}. Thus Pn − F has at
most three components, a contradiction.
5 Concluding remarks
In this paper, we study the l-component (edge) connectivity of Pn for 3 ≤ l ≤ 5. We
have know that the l-component connectivity of Pn are cκ3(Pn) = 2n − 3 for n ≥ 3,
cκ4(Pn) = 3n − 6 for n ≥ 4, cκ5(Pn) = 4n − 8 for n ≥ 6. Also, for n ≥ 3, we have
know the l-component edge connectivity of Pn are cλ3(Pn) = 2n− 3, cλ4(Pn) = 3n− 5,
cλ5(Pn) = 4n− 7. We study the larger component (edge) connectivity of Pn in the future
work.
ORCID iDs
Xiaohui Hua https://orcid.org/0000-0002-1215-3616
Lulu Yang https://orcid.org/0000-0002-7801-4862
References
[1] S. B. Akers and B. Krishnamurthy, A group-theoretic model for symmetric interconnection
networks, IEEE Trans. Comput. 38 (1989), 555–566, doi:10.1109/12.21148, https://doi.
org/10.1109/12.21148.
[2] J. A. Bondy and U. S. R. Murty, Graph Theory, Springer-Verlag, New York, 2008, https:
//link.springer.com/book/9781846289699.
[3] J.-M. Chang, K.-J. Pai, R.-Y. Wu and J.-S. Yang, The 4-component connectivity of alternat-
ing group networks, Theor. Comput. Sci. 766 (2019), 38–45, doi:10.1016/j.tcs.2018.09.018,
https://doi.org/10.1016/j.tcs.2018.09.018.
[4] Y.-C. Chen and J. J. M. Tan, Restricted connectivity for three families of interconnection net-
works, Appl. Math. Comput. 188 (2007), 1848–1855, doi:10.1016/j.amc.2006.11.085, https:
//doi.org/10.1016/j.amc.2006.11.085.
[5] P. E. C. Compeau, Girth of pancake graphs, Discrete Appl. Math. 159 (2011), 1641–1645, doi:
10.1016/j.dam.2011.06.013, https://doi.org/10.1016/j.dam.2011.06.013.
[6] S. Dilixiati, E. Sabir and J. Meng, Star structure connectivities of pancake graphs and burnt pan-
cake graphs, Int. J. Parallel Emerg. Distrib. Syst. 36 (2021), 440–448, doi:10.1080/17445760.
2021.1941006, https://doi.org/10.1080/17445760.2021.1941006.
[7] T. Ding, P. Li and M. Xu, The component (edge) connectivity of shuffle-cubes, Theor. Comput.
Sci. 835 (2020), 108–119, doi:10.1016/j.tcs.2020.06.015, https://doi.org/10.1016/
j.tcs.2020.06.015.
X. Hua and L. Yang: Component (edge) connectivity of pancake graphs 13
[8] L. L. G. Chartrand, S.F. Kapoor and D. Lick, Generalized connectivity in graphs, Bull. Bombay
Math. Colloq. 2 (1984), 1–6.
[9] M.-M. Gu and J.-M. Chang, Neighbor connectivity of pancake graphs and burnt pancake
graphs, Discrete Appl. Math. 324 (2023), 46–57, doi:10.1016/j.dam.2022.09.013, https:
//doi.org/10.1016/j.dam.2022.09.013.
[10] J. Guo and M. Lu, The extra connectivity of bubble-sort star graphs, Theor. Comput. Sci. 645
(2016), 91–99, doi:10.1016/j.tcs.2016.06.043, https://doi.org/10.1016/j.tcs.
2016.06.043.
[11] J. Guo and M. Lu, Conditional diagnosability of the SPn graphs under the comparison di-
agnosis model, Appl. Math. Comput. 336 (2018), 249–256, doi:10.1016/j.amc.2018.05.009,
https://doi.org/10.1016/j.amc.2018.05.009.
[12] L. Guo, Fault tolerance of bubble-sort networks on components, J. Int. Technol. Sci. 22 (2021),
637–643, https://jit.ndhu.edu.tw/article/view/2520.
[13] L. Guo, M. Zhang, S. Zhai and L. Xu, Relation of extra edge connectivity and component
edge connectivity for regular networks, Int. J. Found. Comput. Sci. 32 (2021), 137–149, doi:
10.1142/S0129054121500076, https://doi.org/10.1142/S0129054121500076.
[14] R.-X. Hao, M.-M. Gu and J.-M. Chang, Relationship between extra edge connectivity and
component edge connectivity for regular graphs, Theor. Comput. Sci. 833 (2020), 41–55, doi:
10.1016/j.tcs.2020.05.006, https://doi.org/10.1016/j.tcs.2020.05.006.
[15] R.-X. Hao, M.-M. Gu and J.-M. Chang, Relationship between extra edge connectivity and
component edge connectivity for regular graphs, Theor. Comput. Sci. 833 (2020), 41–55, doi:
10.1016/j.tcs.2020.05.006, https://doi.org/10.1016/j.tcs.2020.05.006.
[16] L.-H. Hsu, E. Cheng, L. Lipták, J. J. M. Tan, C.-K. Lin and T.-Y. Ho, Component connectivity
of the hypercubes, Int. J. Comput. Math. 89 (2012), 137–145, doi:10.1080/00207160.2011.
638978, https://doi.org/10.1080/00207160.2011.638978.
[17] A. Kanevsky and C. Feng, On the embedding of cycles in pancake graphs, Parallel Comput.
21 (1995), 923–936, doi:10.1016/0167-8191(94)00096-S, https://doi.org/10.1016/
0167-8191(94)00096-S.
[18] E. Konstantinova and A. Medvedev, Small cycles in the pancake graph, Ars Math. Contemp.
7 (2014), 237–246, doi:10.26493/1855-3974.214.0e8, https://doi.org/10.26493/
1855-3974.214.0e8.
[19] C.-K. Lin, H.-M. Huang and L.-H. Hsu, The super connectivity of the pancake graphs and the
super laceability of the star graphs, Theor. Comput. Sci. 339 (2005), 257–271, doi:10.1016/j.
tcs.2005.02.007, https://doi.org/10.1016/j.tcs.2005.02.007.
[20] C.-K. Lin, L. Zhang, J. Fan and D. Wang, Structure connectivity and substructure connec-
tivity of hypercubes, Theor. Comput. Sci. 634 (2016), 97–107, doi:10.1016/j.tcs.2016.04.014,
https://doi.org/10.1016/j.tcs.2016.04.014.
[21] H. Liu, S. Zhang and D. Li, On g-extra conditional diagnosability of hierarchical cubic
networks, Theor. Comput. Sci. 790 (2019), 66–79, doi:10.1016/j.tcs.2019.04.028, https:
//doi.org/10.1016/j.tcs.2019.04.028.
[22] E. Sampathkumar, Connectivity of a graph - a generalization, J. Comb. Inf. Syst. Sci. 9 (1984),
71–78.
[23] H. Shang, E. Sabir, J. Meng and L. Guo, Characterizations of optimal component cuts of lo-
cally twisted cubes, Bull. Malays. Math. Sci. Soc. (2) 43 (2020), 2087–2103, doi:10.1007/
s40840-019-00792-y, https://doi.org/10.1007/s40840-019-00792-y.
14 Ars Math. Contemp. 23 (2023) #P3.04
[24] N. Wang, J. Meng and Y. Tian, Neighbor-connectivity of pancake networks and burnt pancake
networks, Theor. Comput. Sci. 916 (2022), 31–39, doi:10.1016/j.tcs.2022.03.002, https://
doi.org/10.1016/j.tcs.2022.03.002.
[25] Z. Wang, Y. Mao, S.-Y. Hsieh and J. Wu, On the g-good-neighbor connectivity of graphs,
Theor. Comput. Sci. 804 (2020), 139–148, doi:10.1016/j.tcs.2019.11.021, https://doi.
org/10.1016/j.tcs.2019.11.021.
[26] X. Yu, X. Huang and Z. Zhang, A kind of conditional connectivity of Cayley graphs generated
by unicyclic graphs, Inf. Sci. 243 (2013), 86–94, doi:10.1016/j.ins.2013.04.011, https://
doi.org/10.1016/j.ins.2013.04.011.
[27] Q. Zhang, L. Xu and W. Yang, Reliability analysis of the augmented cubes in terms of the
extra edge-connectivity and the component edge-connectivity, J. Parallel Distrib. Comput.
147 (2021), 124–131, doi:h10.1016/j.jpdc.2020.08.009, https://doi.org/h10.1016/
j.jpdc.2020.08.009.
[28] S. Zhao and W. Yang, Conditional connectivity of folded hypercubes, Discrete Appl. Math.
257 (2019), 388–392, doi:10.1016/j.dam.2018.09.022, https://doi.org/10.1016/j.
dam.2018.09.022.
[29] S.-L. Zhao, R.-X. Hao and E. Cheng, Two kinds of generalized connectivity of dual cubes,
Discrete Appl. Math. 257 (2019), 306–316, doi:10.1016/j.dam.2018.09.025, https://doi.
org/10.1016/j.dam.2018.09.025.
[30] S. Zhou and X. Li, Conditional fault diagnosability of pancake graphs, J. Converg. Inf. Technol.
8 (2013), 668–675.