# The Pessimistic Diagnosability of Folded Petersen Cubes

Authors: Yingli Kang; Shuai Ye; Weidong Fu; Jing Zhu
Journal: Journal of Mathematics
 (2022)

---

## Abstract

Diagnosability is an important metric parameter for measuring the reliability of multiprocessor systems. The pessimistic diagnosis strategy is a classic diagnostic model based on the PMC model. The class of folded Petersen cubes, denoted byFPQn,k, where n,k≥0 and n,k≠0,0, is introduced as a competitive model of the hypercubes, which is constructed by iteratively applying the Cartesian product operation on the hypercube Qn and the Petersen graph P. In this paper, by exploring the structural properties of the folded Petersen cubes FPQn,k, we first prove that FPQn,k is n+3k diagnosable under the PMC model. Then, we completely derive that the pessimistic diagnosability of FPQn,k is 2n+6k−2 under the PMC model. Furthermore, the diagnosability and the pessimistic diagnosability of the class of folded Petersen cubes, including the hypercube, folded Petersen graph, and hyper Petersen graph, are obtained.


---

## Body

## 1. Introduction

A multiprocessor system can be modeled as a graph, in which nodes (vertices) and edges correspond to processor and communication links, respectively. Throughout the paper, a graph and a system, a vertex and a processor, and an edge and a link are interchangeable.The multiprocessor system has been increasingly adopted in the semiconductor technology, and the system reliability is crucial for multiprocessor systems. To maintain high reliability, multiprocessor systems should differentiate between fault-free processors and faulty ones. Determining all faulty processors is known asfault diagnosis. When all faulty processors can be evaluated precisely and t is an upper bound of the number of faulty processors, we call the multiprocessor system as t-diagnosable. The largest cardinality of the faulty set is named as the diagnosability of this system. Diagnosability of many famous networks had been studied; see [1–5] etc.For the purpose of self-diagnosis of a system, several models have been proposed for diagnosing faulty processors in a multiprocessor system. Among the proposed models, the PMC model [6] was widely used. The PMC model allows each processor to perform diagnosis by testing the neighboring processors and observing their responses.Observe that under at-diagnosable system, a node can only be tested by its neighbors. It is impossible to determine whether some processor v is fault free or not when all the neighbors of v are faulty. To improve the diagnosability, Kavianpour and Friedman [7] proposed the pessimistic diagnosis strategy, which is a classic strategy based on the PMC model. In this strategy, all faulty processors can be isolated within a set which has at most one fault-free processor.Definition 1.
LetG=VG,EG be a system. G is t/t-diagnosable if all faulty processors can be isolated within a set of size at most t such that at most, one fault-free processor is mistaken as a faulty one and the number of faulty processors is bounded by t. The pessimistic diagnosability of G is tpG=maxt:G is t/t- diagnosable}.Using the PMC model with a pessimistic strategy, the pessimistic diagnosability has been receiving much attention for many well-known multiprocessor systems, such as hypercubesQn, Mo¨bius cubes MQn, enhanced hypercubes EQn,s, k-ary n-cubes Qnk, alternating group graphs AGn, hypercube-like network HLn, star graph Sn, and split-star networks Sn2; see Table 1. More desired results can be found in [8–14] and the references therein.Table 1
Pessimistic diagnosability of several main multiprocessor systems.
Multiprocessor systemsGDegreetpGHypercubesQnn2n−2 [15]Mo¨bius cubes MQnn2n−2 [16]Enhanced hypercubesEQn,sn2n−2 [17]3-Ary n-cubes Qn32n4n−3 [8]k-Ary n-cubes Qnk, k≥42n4n−2 [8]Alternating group graphsAGn2n−44n−11 [18]Hypercube-like networkHLnn2n−2 [19]Star graphSnn−12n−4 [20]Split-star networksSn22n−34n−9 [11, 21]Alternating group networksANnn−12n−5 [21]n,k arrangement graphs An,kkn−k2k−1n−k−1 [9]n,k star graphs Sn,kn−1n+k−3 [9]Balanced hypercubesBHn2n2n [9]Data center networksDk,nn+k−1n+2k−2 [22]Cayley graphs generatedΓnSEA2EA−2 (A is triangle free) [23]By transposition graphA2EA−3 (A has a triangle) [23]Bubble-sort star graphsBSn2n−34n−9 [24]Augmented cubesAQn2n−14n−8 [25]Augmented3-ary n-cubes AQn,34n−28n−11 [24]Augmentedk-ary n-cubes AQn,k, k≥44n−28n−10 [24]⋯⋯⋯Network topology is an important factor because it affects the performance of the network. Hypercubes [26] have been recognized as topologies of multiprocessor systems. The class of folded Petersen cubes, proposed by O¨hring and Das [27], is constructed by iteratively applying the Cartesian product operation on hypercubes and the Petersen graph [28–30]. For recent research about folded Petersen cubes, please refer to [31–33] etc.Although there are many results about diagnosability and the pessimistic diagnosability of many multiprocessor systems, little is known for folded Petersen cubes. In this paper, by exploring the structural properties of the folded Petersen cubesFPQn,k, we prove that FPQn,k is n+3k diagnosasable under the PMC model. Then, we completely determine the pessimistic diagnosability of FPQn,k under the PMC model. Furthermore, the diagnosability and the pessimistic diagnosability of the class of folded Petersen cubes, including the hypercube, folded Petersen graph, and hyper Petersen graph, are obtained.


## 2. Preliminaries

### 2.1. Terminologies and Notations

We provide Table2 that contains most of the important notations used in this paper.Table 2
Notations.
SymbolMeaningG=VG,EGAn undirected graph, whereVG is the set of processors and EG is the set of communication links between two processorsNGcThe set of all nodes adjacent toc in GNGV′=⋃v∈V′NGv−V′The neighborhood of a setV′ of nodes in GGV′The subgraph ofG induced by a subset V′⊆VGG−SA graph obtained fromG by removing a node (edge) set SκGThe connectivity ofGG□HThe Cartesian product of two graphsG and HS1ΔS2The symmetric difference of two setsS1 and S2tGThe diagnosability ofGtpGThe pessimistic diagnosability ofGLetG=VG,EG describe the link situation for a simple multiprocessor system. The processors in this system are denoted by an vertex setVG, and the links between each pair of processors are denoted by an edge setEG. Let c be a processor. Denote by NGc the set of processors which have a link to c. For a set V′⊆VG, define NGV′=⋃v∈V′NGv−V′, named as the neighborhood of V′.A graphH is a subgraph of a graph G if VH⊆VG and EH⊆EG. We say that a simple graph is kregular when each processor has exactly k neighbors. For any V′⊆VG with V′≤k−1, if G−V′ is still connected, then, G is k-connected. The maximally connected subgraphs of a graph G are its components. If a component has only one vertex, it is called trivial; otherwise, it is called nontrivial. Let V′⊆VG be a vertex cut, the biggest component of G−V′ is called a large component, and the remaining ones are called small components. Let κG=minS:G−S is disconnected} be the connectivity of G.Suppose thatG and H are two graphs with VG=VH. Let M be a perfect matching between the nodes of G and H. Then, GG,H:M is the graph with node set VG∪VH and edge set EG∪EH∪M.


### 2.2. Folded Petersen Cube

LetG=VG,EG and H=VH,EH be two graphs. The Cartesian product of G and H, denoted by G□H, is the graph with node set VG×VH=g,h:g∈VG,h∈VH, and the vertices g1,h1 and g2,h2 are adjacent if and only if g1=g2 and h1,h2∈EH or h1=h2 and g1,g2∈EG. Under isomorphism, the operator □ is associative and commutative. For any graph G and any positive integer k, we define G1=G and Gk=Gk−1□G if k>1. The hypercubeQn (where n≥1) is defined as Q1=K2 and Qn=Qn−1□Q1. Thus, we also write Qn=K2n.The Petersen graphP was introduced by Chartrand and Wilson [28]; see Figure 1. Obviously, the Petersen graph has an outer 5 cycle, an inner 5 cycle, and five spokes joining them. For k≥1, FPk=Pk represents the k-dimensional folded Petersen graph and HPn=P□Qn−3 (where n≥3) represents the hyper Petersen graph [34].Figure 1
The Petersen graphP.For anyi∈0,1,⋯,9, denote by iFPk−1 the subgraph of FPk induced by the node set ixk−2xk−3⋯x0:xj∈0,1,⋯,9and0≤j≤k−2. Thus, FPk is recursively constructed from iFPk−1 for 0≤i≤9. For any two nodes x and y of FPk, suppose that x=x1x2⋯xk and y=y1y2⋯yk. If x,y∈ViFPk−1, then, x and y are adjacent if and only if x2⋯xk and y2⋯yk are adjacent in FPk−1; otherwise, x and y are adjacent if and only if x1 is adjacent to y1 in P and x2⋯xk=y2⋯yk.From the construction of folded Petersen graphs, it is obvious that any node ofViFPk−1 has 3k−1 neighbors in iFPk−1 and other three neighbors (called extra neighbors) in VjFPk−1, where i and j are adjacent in P.Lemma 2 (see [27]).
The folded Petersen graphFPk is a node and edge transitive regular graph of degree 3k and of node connectivity κFPk=3k. For a node x∈ViFPk−1, the three extra neighbors of x are in distinct jFPk−1, where i and j are adjacent in P. Furthermore, for any two nodes u,v∈ViFPk−1, NiFPk−1¯u∩NiFPk−1¯u=∅, where iFPk−1¯=FPk−iFPk−1.
The class offolded Petersen cubesFPQn,k=Pk□Qn, where n≥0, k≥0 and n,k≠0,0, was introduced as a competitive model of the hypercubes. In particular, FPQ0,k=Pk and FPQn,0=Qn. Clearly, FPQn,k is a triangle-free n+3k-regular graph with 10k2n vertices.Lemma 3 (see [27]).
The folded Petersen cubeFPQn,k is a regular graph with degree n+3k and connectivity κFPQn,k=n+3k. Furthermore, FPQn,kn≥1 can be viewed as GFPQn−1,k,FPQn−1,k:M, where M is a perfect matching between two FPQn−1,k’s.


### 2.3. PMC Model

In self-diagnosable systems, there are several methods which had been introduced to diagnose faulty processors. The PMC model [6] allows each processor to perform diagnosis by testing the neighboring processors and observing their responses. In the PMC model, a test syndromeσ collects all test results. Let S⊆VG. S is said to be compatible with a syndrome σ if σ can be produced from the condition that all nodes in S are faulty and all nodes in VG\S are fault free. Let σS=σ:σ is compatible with S. Two distinct sets S1,S2⊆VG are indistinguishable if σS1∩σS2≠∅ and distinguishable otherwise. The symmetric difference of two sets L1 and L2 is L1ΔL2=L1\L2∪L2\L1.Dahbura and Masson [35] proposed a characterization for a pair of sets to be distinguishable under the PMC model.Lemma 4 (see [35]).
LetG=VG,EG be a graph. For any two distinct sets S1,S2⊆VG, S1,S2 is a distinguishable pair under the PMC model if and only if there exist two nodes u∈VG\S1∪S2 and v∈S1ΔS2 satisfying u,v∈EG; see Figure 2.Figure 2
A distinguishable pairS1,S2.


## 2.1. Terminologies and Notations

We provide Table2 that contains most of the important notations used in this paper.Table 2
Notations.
SymbolMeaningG=VG,EGAn undirected graph, whereVG is the set of processors and EG is the set of communication links between two processorsNGcThe set of all nodes adjacent toc in GNGV′=⋃v∈V′NGv−V′The neighborhood of a setV′ of nodes in GGV′The subgraph ofG induced by a subset V′⊆VGG−SA graph obtained fromG by removing a node (edge) set SκGThe connectivity ofGG□HThe Cartesian product of two graphsG and HS1ΔS2The symmetric difference of two setsS1 and S2tGThe diagnosability ofGtpGThe pessimistic diagnosability ofGLetG=VG,EG describe the link situation for a simple multiprocessor system. The processors in this system are denoted by an vertex setVG, and the links between each pair of processors are denoted by an edge setEG. Let c be a processor. Denote by NGc the set of processors which have a link to c. For a set V′⊆VG, define NGV′=⋃v∈V′NGv−V′, named as the neighborhood of V′.A graphH is a subgraph of a graph G if VH⊆VG and EH⊆EG. We say that a simple graph is kregular when each processor has exactly k neighbors. For any V′⊆VG with V′≤k−1, if G−V′ is still connected, then, G is k-connected. The maximally connected subgraphs of a graph G are its components. If a component has only one vertex, it is called trivial; otherwise, it is called nontrivial. Let V′⊆VG be a vertex cut, the biggest component of G−V′ is called a large component, and the remaining ones are called small components. Let κG=minS:G−S is disconnected} be the connectivity of G.Suppose thatG and H are two graphs with VG=VH. Let M be a perfect matching between the nodes of G and H. Then, GG,H:M is the graph with node set VG∪VH and edge set EG∪EH∪M.


## 2.2. Folded Petersen Cube

LetG=VG,EG and H=VH,EH be two graphs. The Cartesian product of G and H, denoted by G□H, is the graph with node set VG×VH=g,h:g∈VG,h∈VH, and the vertices g1,h1 and g2,h2 are adjacent if and only if g1=g2 and h1,h2∈EH or h1=h2 and g1,g2∈EG. Under isomorphism, the operator □ is associative and commutative. For any graph G and any positive integer k, we define G1=G and Gk=Gk−1□G if k>1. The hypercubeQn (where n≥1) is defined as Q1=K2 and Qn=Qn−1□Q1. Thus, we also write Qn=K2n.The Petersen graphP was introduced by Chartrand and Wilson [28]; see Figure 1. Obviously, the Petersen graph has an outer 5 cycle, an inner 5 cycle, and five spokes joining them. For k≥1, FPk=Pk represents the k-dimensional folded Petersen graph and HPn=P□Qn−3 (where n≥3) represents the hyper Petersen graph [34].Figure 1
The Petersen graphP.For anyi∈0,1,⋯,9, denote by iFPk−1 the subgraph of FPk induced by the node set ixk−2xk−3⋯x0:xj∈0,1,⋯,9and0≤j≤k−2. Thus, FPk is recursively constructed from iFPk−1 for 0≤i≤9. For any two nodes x and y of FPk, suppose that x=x1x2⋯xk and y=y1y2⋯yk. If x,y∈ViFPk−1, then, x and y are adjacent if and only if x2⋯xk and y2⋯yk are adjacent in FPk−1; otherwise, x and y are adjacent if and only if x1 is adjacent to y1 in P and x2⋯xk=y2⋯yk.From the construction of folded Petersen graphs, it is obvious that any node ofViFPk−1 has 3k−1 neighbors in iFPk−1 and other three neighbors (called extra neighbors) in VjFPk−1, where i and j are adjacent in P.Lemma 2 (see [27]).
The folded Petersen graphFPk is a node and edge transitive regular graph of degree 3k and of node connectivity κFPk=3k. For a node x∈ViFPk−1, the three extra neighbors of x are in distinct jFPk−1, where i and j are adjacent in P. Furthermore, for any two nodes u,v∈ViFPk−1, NiFPk−1¯u∩NiFPk−1¯u=∅, where iFPk−1¯=FPk−iFPk−1.
The class offolded Petersen cubesFPQn,k=Pk□Qn, where n≥0, k≥0 and n,k≠0,0, was introduced as a competitive model of the hypercubes. In particular, FPQ0,k=Pk and FPQn,0=Qn. Clearly, FPQn,k is a triangle-free n+3k-regular graph with 10k2n vertices.Lemma 3 (see [27]).
The folded Petersen cubeFPQn,k is a regular graph with degree n+3k and connectivity κFPQn,k=n+3k. Furthermore, FPQn,kn≥1 can be viewed as GFPQn−1,k,FPQn−1,k:M, where M is a perfect matching between two FPQn−1,k’s.


## 2.3. PMC Model

In self-diagnosable systems, there are several methods which had been introduced to diagnose faulty processors. The PMC model [6] allows each processor to perform diagnosis by testing the neighboring processors and observing their responses. In the PMC model, a test syndromeσ collects all test results. Let S⊆VG. S is said to be compatible with a syndrome σ if σ can be produced from the condition that all nodes in S are faulty and all nodes in VG\S are fault free. Let σS=σ:σ is compatible with S. Two distinct sets S1,S2⊆VG are indistinguishable if σS1∩σS2≠∅ and distinguishable otherwise. The symmetric difference of two sets L1 and L2 is L1ΔL2=L1\L2∪L2\L1.Dahbura and Masson [35] proposed a characterization for a pair of sets to be distinguishable under the PMC model.Lemma 4 (see [35]).
LetG=VG,EG be a graph. For any two distinct sets S1,S2⊆VG, S1,S2 is a distinguishable pair under the PMC model if and only if there exist two nodes u∈VG\S1∪S2 and v∈S1ΔS2 satisfying u,v∈EG; see Figure 2.Figure 2
A distinguishable pairS1,S2.


## 3. Main Results

In this section, we first study the structure properties ofFPQn,k. Using the structural properties and some basic lemmas, we can obtained the diagnosability and the pessimistic diagnosability of the folded Petersen cube network FPQn,k.The following inequalities are useful for our proof.Lemma 5.
Letn and k be non-negative integers with n≥0, k≥0 and n,k≠0,0. The following inequalities hold.
(1)10k2n−1≥3n+9k−5,10k2n≥2n+6k+1,10k2n≥5n+15k−6.Proof.
Since the proof for the three statements are similar, we just prove (1), and the proof for (2) and (3) are left for readers.The following is the proof by induction onk.The initial step is as follows: ifk=0, then, 2n−1≥3n−5 holds for any integer n≥1. If k=1, then, 10×2n−1≥3n+4 holds for any integer n≥0.The induction step is as follows: assume thatk≥2 and the statement holds for k−1, i.e., 10k−12n−1≥3n+9k−1−5. Then,
(2)10k2n−1−3n+9k−5≥103n+9k−1−5−3n+9k−5=27n+81k−135>0.Hence, the statement holds fork as well.


### 3.1. Structure Properties ofFPQn,k

Lemma 6 (see [16]).
LetG be a connected graph and S⊆VG. If VG−S≥κG, then, NGS≥κG; otherwise, NGS=VG−S.Lemma 7.
Ifu and v are two distinct nodes in FPQn,k with n≥0, k≥0, and n,k≠0,0, then, NFPQn,ku,v≥2n+6k−2.Proof.
Ifu and v are adjacent, then, NFPQn,ku,v=2n+3k−u,v=2n+6k−2 by Lemma 3; otherwise, since FPQn,k has no triangles, any two nonadjacent nodes have at most one common neighbor, and therefore, NFPQn,ku,v≥2n+3k−1>2n+6k−2.Lemma 8.
LetS be a subset of VFPk for k≥1. If 2≤S≤6k−4, then, NFPkS≥6k−2.Proof.
The lemma is proved by the induction onk. If k=1, then, S=2; the result holds by Lemma 7. Assume that the lemma is true for FPm, where m is an integer with 2≤m≤k−1. In the following, we consider FPk. Recall that FPk is constructed by 10 disjoint FPk−1s, denoted by iFPk−1 for i∈0,1,⋯,9. Let Si=S∩ViFPk−1 and iFPk−1¯=FPk−iFPk−1 for i∈0,1,⋯,9. W.l.o.g., we may assume that S0=maxi∈0,1,⋯,9Si. There are the following cases.Case 1.
S0=1.In this case, for alli∈0,1,⋯,9, Si≤1. Clearly, 2≤S≤10 because of i≤9. If S=2, then, by Lemma 7, we know the result holds. Now, assume that 3≤S≤10 and Si≠∅ for i∈0,1,2. By Lemma 2, N0FPk−1∪1FPk−1∪2FPk−1¯S0≥1. Since FPk is 3k regular and iFPk−1 is isomorphic to FPn−1, we have
(3)NFPkS≥3κiFPk−1+N0FPk−1∪1FPk−1∪2FPk−1¯S0=33k−3+1=9k−8≥6k−2,for k≥2.Case 2.
2≤S0≤6k−10.By inductive hypothesis in0FPk−1, N0FPk−1S0≥6k−1−2=6k−8. We distinguish the following two cases.Case 2.1.
S=S0.By Lemma2, we know
(4)NFPkS=N0FPk−1S0+N0FPk−1¯S0≥6k−8+3S1≥6k−2.Case 2.2.
S≠S0.There exists aj∈1,2,⋯,9 such that Sj≠0. By Lemma 2,
(5)N0FPk−1∪jFPk−1¯S0≥2S0≥4.IfSj=1, then, NjFPk−1Sj=κjFPk−1=3k−3. Note that 0FPk−1 and jFPk−1 are node disjoints; we have
(6)NFPkS≥N0FPk−1S0+NjFPk−1Sj+N0FPk−1∪jFPk−1¯S0≥6k−8+3k−3+4=9k−7≥6k−2,for k≥2.Now, consider2≤Sj≤S0≤6k−10. By induction hypothesis in jFPk−1,
(7)NjFPk−1Sj≥6k−1−2=6k−8.Thus,(8)NFPkS≥N0FPk−1S0+NjFPk−1Sj+N0FPk−1∪jFPk−1¯S0≥26k−8+4=12k−12≥6k−2,for k≥2.Case 3.
6k−9≤S0≤6k−4.Sinceκ0FPk−1=3k−3 and
(9)10k−1−S0≥10k−1−6k−4≥3k−3=κ0FPk−1.Fork≥2, we have N0FPk−1S0≥3k−3 by Lemma 6 and N0FPk−1¯S0=3S0 by Lemma 2. We distinguish the following two cases.Case 3.1.
S=S0.By Lemma2, we know
(10)NFPkS=N0FPk−1S0+N0FPk−1¯S0≥3k−3+36k−9=21k−30≥6k−2,for k≥2.Case 3.2.
S≠S0.There existsj∈1,2,⋯,9 such that Sj≠0. Since S≤6k−4 and S−S0≤5, we have 1≤Sj≤5. Recall that κjFPk−1=3k−3. If Sj=1, then,
(11)NjFPk−1Sj=κjFPk−1=3k−3.If2≤Sj≤5, then,
(12)10k−1−Sj≥10k−1−5≥3k−3=κ0FPk−1,for k≥2, and therefore, NjFPk−1Sj≥3k−3 by Lemma 6. Hence, we have
(13)NFPkS≥N0FPk−1S0+NjFPk−1Sj+N0FPk−1∪jFPk−1¯S0≥3k−3+3k−3+2S0≥6k−6+26k−9=18k−24≥6k−2,for k≥2.Lemma 9.
ForS⊆VQn with n≥3 and 2≤S≤2n−4, it holds that NQnS≥2n−2.Proof.
Proof by induction onn.
Ifn=3, then S=2 and the result holds by Lemma 7. Assume that the lemma is true for Qm with 4≤m≤n−1. Now, we consider Qn as follows. Recall that Qn is constructed by two disjoint Qn−1s, denoted by Q0 and Q1. For i∈1,2, let Si=S∩VQi. W.l.o.g., we may assume that S0≥S1. Since Qn is n regular and triangle free, if S=2, then, NQnS≥2n−2. Next, let 3≤S≤2n−4. It follows that S0≥2. We distinguish the following two cases.Case 1.
2≤S0≤2n−6.By the induction hypothesis inQ0, NQ0S0≥2n−4.IfS1=0, thenm S=S0.Thus,
(14)NQnS≥NQ0S0+NQ0¯S0≥2n−4+2=2n−2.IfS1=1, then, NQ1S1=κQ1=n−1.Thus,
(15)NQnS≥NQ0S0+NQ1S1≥2n−4+n−1=3n−5≥2n−2.It remains to assume that2≤S1≤S0≤2n−6. Then, NQ1S1≥2n−4. Thus,
(16)NQnS≥NQ0S0+NQ1S1≥22n−4=4n−8≥2n−2.Case 2.
2n−5≤S0≤2n−4.SinceκQ0=Q0 is n−1 and VQ0−2n−4≥κQ0=n−1 for n≥4, Lemma 6 implies that NQ0S0≥n−1.IfS=S0, then,
(17)NQnS=NQ0S0+NQ1S0≥n−1+2n−5=3n−6≥2n−2.IfS≠S0, then, S1=1. Thus,
(18)NQnS≥NQ0S0+NQ1S1≥n−1+n−1=2n−2.Therefore, the lemma is true forQn as well.Lemma 10.
ForS⊆VFPQn,k with 2≤S≤2n+6k−4, n≥0, k≥0, and n,k≠0,0, it holds that NFPQn,kS≥2n+6k−2.Proof.
Proof by induction onn.Ifn=0, then, k≥1 and 2≤S≤6k−4; the lemma holds by Lemma 8.Assumen≥1 and the result holds for FPQn−1,k. We consider the result for FPQn,k as follows.Ifk=0, then, 2≤S≤2n−4, the lemma holds by Lemma 9. So, let k≥1.By Lemma3, we know that FPQn,k can be viewed as GFPQn−1,k,FPQn−1,k:M, where M is a perfect matching between two FPQn−1,k’s. In other words, FPQn,k contains two copies of FPQn−1,k, denoted by FPQn−1,k0 and FPQn−1,k1, respectively. For i∈0,1, let Si=S∩VFPQn−1,ki. W.l.o.g., we may assume that S0≥S1.IfS=2, the result holds by Lemma 7. Next, let 3≤S≤2n+6k−4. It implies that S0≥2. We distinguish the following two cases.Case 1.
Let2≤S0≤2n+6k−6.By the induction hypothesis inFPQn−1,k0,
(19)NFPQn−1,k0S0≥2n+6k−4.IfS1=0, then, S=S0. It leads to
(20)NFPQn,kS≥NFPQn−1,k0S0+NFPQn−1,k0¯S0≥2n+6k−4+2=2n+6k−2.IfS1=1, then NFPQn−1,k1S1=κFPQn−1,k1=n+3k−1.Thus,
(21)NFPQn,kS≥NFPQn−1,k0S0+NFPQn−1,k1S1≥2n+6k−4+n+3k−1≥2n+6k−2.It remains to assume that2≤S1≤S0≤2n+6k−6. Then,
(22)NFPQn−1,k1S1≥2n+6k−4.Thus,(23)NFPQn,kS≥NFPQn−1,k0S0+NFPQn−1,k1S1≥22n+6k−4≥2n+6k−2.Case 2.
Let2n+6k−5≤S0≤2n+6k−4.In this case, we have(24)VFPQn−1,k0−2n+6k−4=10k2n−1−2n+6k−4≥n+3k−1=κFPQn−1,k0,where the inequality follows from Lemma 5 (1). By Lemma 6, NFPQn−1,k0S0≥n+3k−1.IfS=S0, then,
(25)NFPQn,kS=NFPQn−1,k0S0+NFPQn−1,k1S0≥n+3k−1+2n+6k−5=3n+9k−6≥2n+6k−2.IfS≠S0, then, S1=1. Thus,
(26)NFPQn,kS≥NFPQn−1,k0S0+NFPQn−1,k1S1≥n+3k−1+n+3k−1=2n+6k−2.


### 3.2. T-Diagnosability ofFPQn,k

In what follows, we will discuss the diagnosability ofFPQn,k under the PMC model.Lemma 11.
LetFPQn,k be the folded Petersen cube for n≥0, k≥0 and n,k≠0,0. Then, tFPQn,k≤n+3k under the PMC model.Proof.
Letv0 be any vertex in FPQn,k. Let L1=NFPQn,kv0 and L2=NFPQn,kv0∪v0. Assume that both L1 and L2 are faulty sets. Obviously, L1=n+3k<n+3k+1, L2=n+3k+1, L1∪L2=L2≠VFPQn,k, and L1ΔL2=v0. If L1 and L2 are distinguishable under the PMC model, then, there exists some vertex x∈VFPQn,k\F1∪F2 such that x,v0∈EFPQn,k, a contradiction. Thus, L1 and L2 are indistinguishable under the PMC model. It leads to tFPQn,k≤L2−1=n+3k.Lemma 12.
LetFPQn,k be the folded Petersen cube for n≥0, k≥0 and n,k≠0,0. Then, tFPQn,k≥n+3k under the PMC model.Proof.
LetL1 and L2 be two distinct faulty sets such that L1,L2≤n+3k. Since L1 and L2 are distinct, L1ΔL2≠∅, which implies that L2\L1≠∅ or L1\L2≠∅. W.l.o.g., let L1\L2≠∅. To complete the proof, it is sufficient to show that L1 and L2 are distinguishable under the PMC model.
Suppose to the contrary thatL1 and L2 are indistinguishable. If VFPQn,k\L1∪L2=∅, then, L1∪L2=VFPQn,k. Since VFPQn,k=10k2n, we have L1+L2≥L1∪L2=10k2n>2n+3k, a contradiction to the assumption. Thus, VFPQn,k\L1∪L2≠∅. Since the assumption that L1 and L2 are indistinguishable under the PMC model, there exist no edges between L1ΔL2 and VFPQn,k\L1∪L2. Note that FPQn,k is connected. So, L1∩L2 is a vertex cut of FPQn,k and L1∩L2≥κFPQn,k=n+3k. Recall that L1\L2≠∅, i.e., L1\L2≥1. Thus,
(27)L1=L1\L2+L1∩L2≥n+3k+1,a contradiction.The following theorem follows directly from the previous two lemmas.Theorem 13.
LetFPQn,k be the folded Petersen cube for n≥0, k≥0 and n,k≠0,0. Then, tFPQn,k=n+3k under the PMC model.The following corollaries are a straightforward consequence of Theorem13.Corollary 14.
LetQn be the n-dimensional hypercube. Then, tQn=n under the PMC model.Corollary 15.
LetFPk be the k-dimensional folded Petersen graph. Then, tFPk=3k under the PMC model.Corollary 16.
LetHPn=P□Qn−3 (where n≥3) be the hyper Petersen graph. Then, tHPn=n under the PMC model.


### 3.3. Pessimistic Diagnosability ofFPQn,k

Chwa and Hakimi [36] derived a characterization for a graph to be t/t diagnosability.Lemma 17 (see [36]).
LetG=VG,EG be the representation of a system. G is t/t diagnosable if and only if for each integer p with 1≤p≤t−1 and each S∗⊆VG with S∗=2t−p; it holds that NGS∗>p.
Tsai and Chen [37] further derived another characterization for a graph to be t/t diagnosability.Lemma 18 (see [37]).
A graphG=VG,EG is t/t diagnosable if and only if for each set S∗⊆VG with 0≤S∗=p≤t−1; the graph G−S∗ has at most one trivial component, and each nontrivial component C of G−S∗ satisfies VC≥2t−p+1.Lemma 19.
LetFPQn,k be the folded Petersen cube for n≥0, k≥0, and n,k≠0,0. Then, for each S∗⊆VFPQn,k with S∗=22n+6k−2−p and 1≤p≤2n+6k−3, it holds that NFPQn,kS∗>p.Proof.
We consider the following two cases according to the value ofp.Case 1.
Let1≤p≤n+3k−1.By the assumption,2n+3k−1≤S∗≤22n+6k−3. Moreover, κFPQn,k=n+3k and 10k2n−22n+6k−3≥n+3k by Lemma 5 (3). Hence, we can deduce that
(28)VFPQn,k−S∗≥10k2n−22n+6k−3≥n+3k=κFPQn,k.By Lemma6, NFPQn,kS∗≥κFPQn,k=n+3k>p.Case 2.
Letn+3k≤p≤2n+6k−3.By the assumption,2≤S∗≤2n+6k−4. By Lemma 8, NFPQn,kS∗≥2n+6k−2>p.Theorem 20.
LetFPQn,k be the folded Petersen cube for n≥0, k≥0 and n,k≠0,0. Then, tpFPQn,k=2n+6k−2.Proof.
By Lemmas17 and 19, tpFPQn,k≥2n+6k−2. It remains to show that tpFPQn,k≤2n+6k−2 for n≥0, k≥0 and n,k≠0,0.Suppose to the contrary thattpFPQn,k≥2n+6k−1. Let u0,v0 be an edge in FPQn,k and let S=NFPQn,ku0,v0. Since FPQn,k has no triangles, S=2n+6k−2≤tpFPQn,k−1. The subgraph C induced by u0,v0 is a connected component of FPQn,k−S. By Lemma 18,
(29)VC≥2tpFPQn,k−S+1≥22n+6k−1−2n+6k−2+1=3,a contradiction.The following corollaries are obvious from Theorem20.Corollary 21.
LetQn be the n-dimensional hypercube. Then, tpQn=2n−2.Corollary 22.
LetFPk be the k-dimensional folded Petersen graph. Then, tpFPk=6k−2.Corollary 23.
LetHPn=P□Qn−3 (where n≥3) be the hyper Petersen graph. Then, tpHPn=2n−2.


## 3.1. Structure Properties ofFPQn,k

Lemma 6 (see [16]).
LetG be a connected graph and S⊆VG. If VG−S≥κG, then, NGS≥κG; otherwise, NGS=VG−S.Lemma 7.
Ifu and v are two distinct nodes in FPQn,k with n≥0, k≥0, and n,k≠0,0, then, NFPQn,ku,v≥2n+6k−2.Proof.
Ifu and v are adjacent, then, NFPQn,ku,v=2n+3k−u,v=2n+6k−2 by Lemma 3; otherwise, since FPQn,k has no triangles, any two nonadjacent nodes have at most one common neighbor, and therefore, NFPQn,ku,v≥2n+3k−1>2n+6k−2.Lemma 8.
LetS be a subset of VFPk for k≥1. If 2≤S≤6k−4, then, NFPkS≥6k−2.Proof.
The lemma is proved by the induction onk. If k=1, then, S=2; the result holds by Lemma 7. Assume that the lemma is true for FPm, where m is an integer with 2≤m≤k−1. In the following, we consider FPk. Recall that FPk is constructed by 10 disjoint FPk−1s, denoted by iFPk−1 for i∈0,1,⋯,9. Let Si=S∩ViFPk−1 and iFPk−1¯=FPk−iFPk−1 for i∈0,1,⋯,9. W.l.o.g., we may assume that S0=maxi∈0,1,⋯,9Si. There are the following cases.Case 1.
S0=1.In this case, for alli∈0,1,⋯,9, Si≤1. Clearly, 2≤S≤10 because of i≤9. If S=2, then, by Lemma 7, we know the result holds. Now, assume that 3≤S≤10 and Si≠∅ for i∈0,1,2. By Lemma 2, N0FPk−1∪1FPk−1∪2FPk−1¯S0≥1. Since FPk is 3k regular and iFPk−1 is isomorphic to FPn−1, we have
(3)NFPkS≥3κiFPk−1+N0FPk−1∪1FPk−1∪2FPk−1¯S0=33k−3+1=9k−8≥6k−2,for k≥2.Case 2.
2≤S0≤6k−10.By inductive hypothesis in0FPk−1, N0FPk−1S0≥6k−1−2=6k−8. We distinguish the following two cases.Case 2.1.
S=S0.By Lemma2, we know
(4)NFPkS=N0FPk−1S0+N0FPk−1¯S0≥6k−8+3S1≥6k−2.Case 2.2.
S≠S0.There exists aj∈1,2,⋯,9 such that Sj≠0. By Lemma 2,
(5)N0FPk−1∪jFPk−1¯S0≥2S0≥4.IfSj=1, then, NjFPk−1Sj=κjFPk−1=3k−3. Note that 0FPk−1 and jFPk−1 are node disjoints; we have
(6)NFPkS≥N0FPk−1S0+NjFPk−1Sj+N0FPk−1∪jFPk−1¯S0≥6k−8+3k−3+4=9k−7≥6k−2,for k≥2.Now, consider2≤Sj≤S0≤6k−10. By induction hypothesis in jFPk−1,
(7)NjFPk−1Sj≥6k−1−2=6k−8.Thus,(8)NFPkS≥N0FPk−1S0+NjFPk−1Sj+N0FPk−1∪jFPk−1¯S0≥26k−8+4=12k−12≥6k−2,for k≥2.Case 3.
6k−9≤S0≤6k−4.Sinceκ0FPk−1=3k−3 and
(9)10k−1−S0≥10k−1−6k−4≥3k−3=κ0FPk−1.Fork≥2, we have N0FPk−1S0≥3k−3 by Lemma 6 and N0FPk−1¯S0=3S0 by Lemma 2. We distinguish the following two cases.Case 3.1.
S=S0.By Lemma2, we know
(10)NFPkS=N0FPk−1S0+N0FPk−1¯S0≥3k−3+36k−9=21k−30≥6k−2,for k≥2.Case 3.2.
S≠S0.There existsj∈1,2,⋯,9 such that Sj≠0. Since S≤6k−4 and S−S0≤5, we have 1≤Sj≤5. Recall that κjFPk−1=3k−3. If Sj=1, then,
(11)NjFPk−1Sj=κjFPk−1=3k−3.If2≤Sj≤5, then,
(12)10k−1−Sj≥10k−1−5≥3k−3=κ0FPk−1,for k≥2, and therefore, NjFPk−1Sj≥3k−3 by Lemma 6. Hence, we have
(13)NFPkS≥N0FPk−1S0+NjFPk−1Sj+N0FPk−1∪jFPk−1¯S0≥3k−3+3k−3+2S0≥6k−6+26k−9=18k−24≥6k−2,for k≥2.Lemma 9.
ForS⊆VQn with n≥3 and 2≤S≤2n−4, it holds that NQnS≥2n−2.Proof.
Proof by induction onn.
Ifn=3, then S=2 and the result holds by Lemma 7. Assume that the lemma is true for Qm with 4≤m≤n−1. Now, we consider Qn as follows. Recall that Qn is constructed by two disjoint Qn−1s, denoted by Q0 and Q1. For i∈1,2, let Si=S∩VQi. W.l.o.g., we may assume that S0≥S1. Since Qn is n regular and triangle free, if S=2, then, NQnS≥2n−2. Next, let 3≤S≤2n−4. It follows that S0≥2. We distinguish the following two cases.Case 1.
2≤S0≤2n−6.By the induction hypothesis inQ0, NQ0S0≥2n−4.IfS1=0, thenm S=S0.Thus,
(14)NQnS≥NQ0S0+NQ0¯S0≥2n−4+2=2n−2.IfS1=1, then, NQ1S1=κQ1=n−1.Thus,
(15)NQnS≥NQ0S0+NQ1S1≥2n−4+n−1=3n−5≥2n−2.It remains to assume that2≤S1≤S0≤2n−6. Then, NQ1S1≥2n−4. Thus,
(16)NQnS≥NQ0S0+NQ1S1≥22n−4=4n−8≥2n−2.Case 2.
2n−5≤S0≤2n−4.SinceκQ0=Q0 is n−1 and VQ0−2n−4≥κQ0=n−1 for n≥4, Lemma 6 implies that NQ0S0≥n−1.IfS=S0, then,
(17)NQnS=NQ0S0+NQ1S0≥n−1+2n−5=3n−6≥2n−2.IfS≠S0, then, S1=1. Thus,
(18)NQnS≥NQ0S0+NQ1S1≥n−1+n−1=2n−2.Therefore, the lemma is true forQn as well.Lemma 10.
ForS⊆VFPQn,k with 2≤S≤2n+6k−4, n≥0, k≥0, and n,k≠0,0, it holds that NFPQn,kS≥2n+6k−2.Proof.
Proof by induction onn.Ifn=0, then, k≥1 and 2≤S≤6k−4; the lemma holds by Lemma 8.Assumen≥1 and the result holds for FPQn−1,k. We consider the result for FPQn,k as follows.Ifk=0, then, 2≤S≤2n−4, the lemma holds by Lemma 9. So, let k≥1.By Lemma3, we know that FPQn,k can be viewed as GFPQn−1,k,FPQn−1,k:M, where M is a perfect matching between two FPQn−1,k’s. In other words, FPQn,k contains two copies of FPQn−1,k, denoted by FPQn−1,k0 and FPQn−1,k1, respectively. For i∈0,1, let Si=S∩VFPQn−1,ki. W.l.o.g., we may assume that S0≥S1.IfS=2, the result holds by Lemma 7. Next, let 3≤S≤2n+6k−4. It implies that S0≥2. We distinguish the following two cases.Case 1.
Let2≤S0≤2n+6k−6.By the induction hypothesis inFPQn−1,k0,
(19)NFPQn−1,k0S0≥2n+6k−4.IfS1=0, then, S=S0. It leads to
(20)NFPQn,kS≥NFPQn−1,k0S0+NFPQn−1,k0¯S0≥2n+6k−4+2=2n+6k−2.IfS1=1, then NFPQn−1,k1S1=κFPQn−1,k1=n+3k−1.Thus,
(21)NFPQn,kS≥NFPQn−1,k0S0+NFPQn−1,k1S1≥2n+6k−4+n+3k−1≥2n+6k−2.It remains to assume that2≤S1≤S0≤2n+6k−6. Then,
(22)NFPQn−1,k1S1≥2n+6k−4.Thus,(23)NFPQn,kS≥NFPQn−1,k0S0+NFPQn−1,k1S1≥22n+6k−4≥2n+6k−2.Case 2.
Let2n+6k−5≤S0≤2n+6k−4.In this case, we have(24)VFPQn−1,k0−2n+6k−4=10k2n−1−2n+6k−4≥n+3k−1=κFPQn−1,k0,where the inequality follows from Lemma 5 (1). By Lemma 6, NFPQn−1,k0S0≥n+3k−1.IfS=S0, then,
(25)NFPQn,kS=NFPQn−1,k0S0+NFPQn−1,k1S0≥n+3k−1+2n+6k−5=3n+9k−6≥2n+6k−2.IfS≠S0, then, S1=1. Thus,
(26)NFPQn,kS≥NFPQn−1,k0S0+NFPQn−1,k1S1≥n+3k−1+n+3k−1=2n+6k−2.


## 3.2. T-Diagnosability ofFPQn,k

In what follows, we will discuss the diagnosability ofFPQn,k under the PMC model.Lemma 11.
LetFPQn,k be the folded Petersen cube for n≥0, k≥0 and n,k≠0,0. Then, tFPQn,k≤n+3k under the PMC model.Proof.
Letv0 be any vertex in FPQn,k. Let L1=NFPQn,kv0 and L2=NFPQn,kv0∪v0. Assume that both L1 and L2 are faulty sets. Obviously, L1=n+3k<n+3k+1, L2=n+3k+1, L1∪L2=L2≠VFPQn,k, and L1ΔL2=v0. If L1 and L2 are distinguishable under the PMC model, then, there exists some vertex x∈VFPQn,k\F1∪F2 such that x,v0∈EFPQn,k, a contradiction. Thus, L1 and L2 are indistinguishable under the PMC model. It leads to tFPQn,k≤L2−1=n+3k.Lemma 12.
LetFPQn,k be the folded Petersen cube for n≥0, k≥0 and n,k≠0,0. Then, tFPQn,k≥n+3k under the PMC model.Proof.
LetL1 and L2 be two distinct faulty sets such that L1,L2≤n+3k. Since L1 and L2 are distinct, L1ΔL2≠∅, which implies that L2\L1≠∅ or L1\L2≠∅. W.l.o.g., let L1\L2≠∅. To complete the proof, it is sufficient to show that L1 and L2 are distinguishable under the PMC model.
Suppose to the contrary thatL1 and L2 are indistinguishable. If VFPQn,k\L1∪L2=∅, then, L1∪L2=VFPQn,k. Since VFPQn,k=10k2n, we have L1+L2≥L1∪L2=10k2n>2n+3k, a contradiction to the assumption. Thus, VFPQn,k\L1∪L2≠∅. Since the assumption that L1 and L2 are indistinguishable under the PMC model, there exist no edges between L1ΔL2 and VFPQn,k\L1∪L2. Note that FPQn,k is connected. So, L1∩L2 is a vertex cut of FPQn,k and L1∩L2≥κFPQn,k=n+3k. Recall that L1\L2≠∅, i.e., L1\L2≥1. Thus,
(27)L1=L1\L2+L1∩L2≥n+3k+1,a contradiction.The following theorem follows directly from the previous two lemmas.Theorem 13.
LetFPQn,k be the folded Petersen cube for n≥0, k≥0 and n,k≠0,0. Then, tFPQn,k=n+3k under the PMC model.The following corollaries are a straightforward consequence of Theorem13.Corollary 14.
LetQn be the n-dimensional hypercube. Then, tQn=n under the PMC model.Corollary 15.
LetFPk be the k-dimensional folded Petersen graph. Then, tFPk=3k under the PMC model.Corollary 16.
LetHPn=P□Qn−3 (where n≥3) be the hyper Petersen graph. Then, tHPn=n under the PMC model.


## 3.3. Pessimistic Diagnosability ofFPQn,k

Chwa and Hakimi [36] derived a characterization for a graph to be t/t diagnosability.Lemma 17 (see [36]).
LetG=VG,EG be the representation of a system. G is t/t diagnosable if and only if for each integer p with 1≤p≤t−1 and each S∗⊆VG with S∗=2t−p; it holds that NGS∗>p.
Tsai and Chen [37] further derived another characterization for a graph to be t/t diagnosability.Lemma 18 (see [37]).
A graphG=VG,EG is t/t diagnosable if and only if for each set S∗⊆VG with 0≤S∗=p≤t−1; the graph G−S∗ has at most one trivial component, and each nontrivial component C of G−S∗ satisfies VC≥2t−p+1.Lemma 19.
LetFPQn,k be the folded Petersen cube for n≥0, k≥0, and n,k≠0,0. Then, for each S∗⊆VFPQn,k with S∗=22n+6k−2−p and 1≤p≤2n+6k−3, it holds that NFPQn,kS∗>p.Proof.
We consider the following two cases according to the value ofp.Case 1.
Let1≤p≤n+3k−1.By the assumption,2n+3k−1≤S∗≤22n+6k−3. Moreover, κFPQn,k=n+3k and 10k2n−22n+6k−3≥n+3k by Lemma 5 (3). Hence, we can deduce that
(28)VFPQn,k−S∗≥10k2n−22n+6k−3≥n+3k=κFPQn,k.By Lemma6, NFPQn,kS∗≥κFPQn,k=n+3k>p.Case 2.
Letn+3k≤p≤2n+6k−3.By the assumption,2≤S∗≤2n+6k−4. By Lemma 8, NFPQn,kS∗≥2n+6k−2>p.Theorem 20.
LetFPQn,k be the folded Petersen cube for n≥0, k≥0 and n,k≠0,0. Then, tpFPQn,k=2n+6k−2.Proof.
By Lemmas17 and 19, tpFPQn,k≥2n+6k−2. It remains to show that tpFPQn,k≤2n+6k−2 for n≥0, k≥0 and n,k≠0,0.Suppose to the contrary thattpFPQn,k≥2n+6k−1. Let u0,v0 be an edge in FPQn,k and let S=NFPQn,ku0,v0. Since FPQn,k has no triangles, S=2n+6k−2≤tpFPQn,k−1. The subgraph C induced by u0,v0 is a connected component of FPQn,k−S. By Lemma 18,
(29)VC≥2tpFPQn,k−S+1≥22n+6k−1−2n+6k−2+1=3,a contradiction.The following corollaries are obvious from Theorem20.Corollary 21.
LetQn be the n-dimensional hypercube. Then, tpQn=2n−2.Corollary 22.
LetFPk be the k-dimensional folded Petersen graph. Then, tpFPk=6k−2.Corollary 23.
LetHPn=P□Qn−3 (where n≥3) be the hyper Petersen graph. Then, tpHPn=2n−2.


## 4. Concluding Remarks

In this paper, by exploring structural properties of the folded Petersen cubesFPQn,k, we prove that FPQn,k is n+3k diagnosasable under the PMC model. Moreover, we study the pessimistic diagnosability of folded Petersen cubes and obtain tpFPQn,k=2n+6k−2 for n≥0, k≥0 and n,k≠0,0. As corollaries, the diagnosability and the pessimistic diagnosability of hypercube, folded Petersen graph, and the hyper Petersen graph are obtained. Another direction of our study in this paper is to investigate the conditional diagnosability of these graphs.



---

*Source: 3114022-2022-10-20.xml*