The 3-extra diagnosability of bubble-sort star graph networks

-,

(School of Mathematics and Computer Science, Shanxi Normal University, Linfen 041004, China)

Abstract： The g-extra diagnosability of G is a new fault diagnosis method for interconnection networks, which limits every good component to at least (g+1) fault free nodes. As a desirable topology structure of interconnection networks, the n-dimensional bubble-sort star graph BSn has some important properties. In this paper, we prove that the 3-extra diagnosability of BSn is 8n-20 under the PMC model for n≥5 and under the MM* model for n≥12.

Key words： interconnection network; connectivity; diagnosability; bubble-sort star graph

Interconnection networks (networks for short) can be regarded as network topologies. A network is represented by a graph where vertices represent processors and edges represent communication links between two processors. We can exchange graphs and networks. For the system, it is of great significance to study the topological properties of its network. Because the processors may fail and cause faults in the system, node fault identification is very important for such systems. To deal with faults, we first identify the fault processors from the fault-free processors. The process of identifying faults is called system diagnosis.

If all faulty processors can be identified without replacement and the number of faulty processors does not exceedt, then this system ist-diagnosable. The diagnosabilityt(G) is the maximum number oftwhereGist-diagnosable[1-4]. Dahbura, et al.[2]proposed an algorithm with time complexO(n2.5) about at-diagnosable system. Some diagnosis models for identifying fault processors are introduced. The main method is the PMC diagnosis model[5]. The diagnosis of the system is that two connected processors test each other. Maeng, et al.[6](MM model) propose another diagnosis model. In the MM model, a node sends the same task to its 2 neighbors, and then compares their responses. Sengupta, et al.(1)Sengupta A, Dahbura A T. On self-diagnosable multiprocessor systems: Diagnosis by the comparison approach[J]. IEEE Transactions on Computers, 1992, 41(11): 1386-1396.put forward a special example of the MM model, called the MM*model, where each node must test any pair of its neighbors. Numerous studies have been investigated under the PMC model, MM model or MM*model (see [3-4,7-11]). In 2005, Lai, et al.[4]introduced conditional diagnosability of systems, which is also called restricted diagnosability. They assume that all neighbors of any vertex in the system are not included in the fault set. The restricted diagnosability of the system has received much attention[12-16]. In 2012, Peng, et al.[10]proposed ag-good neighbor diagnosability (also known asg-good neighbor conditional diagnosability). This method of system fault diagnosis requires each good node to have at leastggood neighbors.In the PMC model, Peng, et al.[10]studied theg-good-neighbor diagnosability of ann-dimensional hypercube. In the MM*model, Wang, et al.[17]studied the diagnosability ofg-good neighbors of then-dimensional hypercube.Theg-good-neighbor diagnosability of the system has received much attention, too [11,16,18-21]. In 2016, Zhang, et al.[22]proposedg-extra diagnosability. It is a new method of system fault-diagnosis, which limits each fault-free component to have at least (g+1) fault-free nodes. Zhang, et al.[22]studied theg-extra diagnosability of then-dimensional hypercube with the PMC model and the MM*model. In 2016, Wang, et al.[23]studied the 2-extra diagnosability of the bubble-sort star graphBSnin PMC model and the MM*model.

The bubble-sort star graph is studied after studying the star graph and the bubble-sort graph. The star graph and the bubble-sort graph have been proved to be an important viable candidate for interconnecting a multiprocessor system[24]. A feature of the star graph includes a low degree of node,small diameter, symmetry, and high degree of fault-tolerance. For details, see [7,25-37]. In Refs.[38-39], the diagnosability of a star graph under the PMC model and the MM model is studied. Lin, et al.[9]showed that the conditional diagnosability of the star graphSnunder the comparison diagnosis model is 3n-7.Guo, et al.[40]showed that the conditional diagnosability of the bubble-sort star graphBSnunder the MM model is 6n-15 forn≥6 and under the PMC model is 8n-21 forn≥5. Using the PMC model and the MM*model, Wang, et al.[23]studied the 2-extra diagnosability ofBSn. Guo, et al.[41]studied the extra connectivity ofBSn.

As a favorable topology structure of interconnection networks, then-dimensional bubble-sort star graphBSnhas many good properties. In this paper, we prove that the 3-extra diagnosability ofBSnis 8n-20 under the PMC model withn≥5 and under the MM*model withn≥12.

1 Preliminaries

In this section, there are some definitions and notations needed for our discussion; then-dimensional bubble-sort star graphBSn, the PMC model and the MM*model are introduced.

1.1 Notations

Table 1 Some symbols in the graph[42]

1.2 The PMC model and the MM* model

In the PMC model[5], to diagnose a systemG, two adjacent nodes inGhave the ability to test each other. Foruv∈E(G), the test performed byuonvis represented by the ordered pair (u,v).The result of testing (u,v) is 1 (resp. 0) ifutestingvis faulty (resp. fault-free). We usually assume that the test results are reliable (resp. unreliable) ifuis fault-free (resp. faulty). The test allocationTof systemGis the test set of each adjacent vertex pair. It is expressed as directed test graph (V(G),L), where (u,v)∈Lmeans thatuv∈E(G). Syndrome is the set of test results for all testsT. A fault set is made up of all fault processors. Given a syndromeσ, ifσsatisfiesu∈VFandσ(u,v) = 1 for any (u,v)∈Liffv∈F, thenF⊆V(G) is consistent withσ.This means thatFmay be faulty processors.Because the test results generated by the faulty processor are not reliable. A setFof faulty vertices may produce many different syndromes.However, different fault sets may cause the same syndrome.Letσ(F) be the set of all syndromes consistent with it.LetF1,F2∈V(G),F1≠F2. Ifσ(F1)∩σ(F2)=∅, then they are distinguishable and we say (F1,F2) is a distinguishable pair, otherwise, they are indistinguishable and (F1,F2) is an indistinguishable pair.

In the MM model[6], the same test task is sent from one processor to a pair of processors and their responses are compared to perform the diagnosis. There are three assumptions: (a) all faults are invariable; (b) the faulty processor produces incorrect output; (c) the comparison performed by the fault processor is not reliable. The comparison of the systemG=(V,E) is transformed into a multigraph, which is represented byM(V(G),L) whereLis the marked edge set.(u,v)w∈Ldenotes a comparison in whichwcomparesuandv, which means thatuw,vw∈E(G). The syndromeσ*represents the set of all comparison results inM(V(G),L). If the results (u,v)ware different, thenσ*((u,v)w)=1. Otherwise,σ*((u,v)w)=0. In the MM*model, ifuw,vw∈E(G), then (u,v)w∈L. Consistent and indistinguishable are similar to those in PMC.

LetF1andF2be a distinct pair ofg-good-neighbor subsets with |F1|≤tand |F2|≤tinV. IfF1andF2are distinguishable for each distinct pair (F1,F2), then the systemG=(V,E) isg-good-neighbort-diagnosable. Theg-good-neighbor diagnosabilitytg(G)=max{t:Gisg-good-neighbort-diagnosable}.

Proposition1[10]For any given systemG,tg(G)≤tg′(G) ifg≤g′.

In a systemG=(V,E), a setF⊆Vis called a conditional set if it does not contain all the neighbor vertices of any vertex inG. A systemGis conditionalt-diagnosable if every two distinct conditional subsetsF1,F2∈Vwith |F1|≤t, |F2|≤t, are distinguishable. The conditional diagnosabilitytc(G)=max{t:Gis conditionalt-diagnosable}. By [8],tc(G)≥t(G).

Theorem1[18]For a systemG=(V,E),t(G)=t0(G)≤t1(G)≤tc(G).

1.3 The bubble-sort star graph

Let [n]={1,2,…,n}, and letSnbe the symmetric group on [n] containing all permutationsp=p1p2…pnof [n]. {(1i): 2≤i≤n} is a generating set forSn. Thus, {(1,i): 2≤i≤n}∪{(i,i+1): 2≤i≤n-1} is a generating set forSn. Then-dimensional bubble-sort star graphBSn[40,45]is the graph with vertex setV(BSn)=Snin which two verticesuv∈E(BSn) iffu=v(1,i), 2≤i≤n, oru=v(i,i+1), 2≤i≤n-1. Clearly,BSnis a (2n-3)-regular graph withn! vertices. The graphsBSnforn=2,3,4 are depicted in Fig.1.

Fig.1 The bubble-sort star graphs BS2, BS3 and BS4

Note thatBSnis a special Cayley graph.BSnhas the following useful properties.

Proposition3For any integern≥1,BSnis (2n-3)-regular, vertex transitive.

Proposition4For any integern≥2,BSnis bipartite.

Theorem4[44]Every nonidentity permutation in the symmetric group is uniquely (up to the order of the factors) a product of disjoint cycles, each of which has length at least 2.

Proposition5[45]LetBSnbe the bubble-sort star graph. Ifuv∈E(BSn), then |N(u)∩N(v)|=0. Ifuv∉E(BSn), then |N(u)∩N(v)|≤3.

Lemma1(2)Wang S. The tightly super 3-extra connectivity of bubble-sort star graphs [J]. RAIRO-Theoretical Informatics and Applications (to appear).LetA={(1),(14),(15), (34)}. Ifn≥5,F1=N(A),F2=A∪N(A), then |F1|=8n-23, |F2|=8n-19,F1is a 3-extra cut ofBSn, andBSn-F1has two componentsBSn-F2andBSn[A].

A connected graphGis superg-extra connected if for each minimumg-extra cutF,G-Fhas a component withg+1 vertices. Besides,G-Fexactly contains 2 components, where one component hasg+1 vertices, thenGis called to be tightly |F| superg-extra connected.

Theorem6①Forn≥5, the bubble-sort star graphBSnis tightly (8n-23) super 3-extra connected.

2 The 3-extra diagnosability of the bubble-sort star graph under the PMC

Theorem7[2,11]A systemG=(V,E) isg-extrat-diagnosable in PMC model iffGhasuv∈E(G) whereu∈V(G-F1-F2) andv∈F1F2orv∈F2F1forg-extra setsF1,F2∈V,F1≠F2, |F1|≤tand |F2|≤t(See Fig. 2).

Fig.2 Illustration of a distinguishable pair (F1, F2) under the PMC model

Corollary1Letn≥5. Then the 3-extra diagnosability of the bubble-sort star graphBSnunder the PMC model is 8n-20.

ProofLetF1andF2be each distinct pair of 3-extra subsetsF1andF2ofBSnwith |F1|≤8n-20 and |F2|≤8n-20. Assume thatV(BSn)=F1∪F2. By the definition of the symmetric groupSn,n!=|Sn|=|F1∪F2|=|F1|+|F2|-|F1∩F2|≤|F1|+|F2|≤2(8n-20)=16n-40. Sincen≥5,n!> 16n-40, a contradiction. Therefore,V(BSn)≠F1∪F2.

□

3 The 3-extra diagnosability of the bubble-sort star graph under the MM*

Theorem9[2,11]A systemG=(V,E) isg-extrat-diagnosable in the MM*model iff forg-extra setsF1,F2∈V,F1≠F2, |F1|≤tand |F2|≤t, they have one of 3 conditions: ①Ghasuw,vw∈E(G) whereu,w∈V(G-F1-F2) andv∈F1F2orv∈F2F1.②Ghasuw,vw∈E(G) whereu,v∈F1F2andw∈V(G-F1-F2).③Ghasuw,vw∈E(G) whereu,v∈F2F1andw∈V(G-F1-F2) (See Fig.3).

Fig.3 Illustration of a distinguishable pair (F1, F2) under the MM* model.

□

A component of a graphGis odd according as it has an odd number of vertices. We denote byo(G) the number of odd components ofG.

Lemma3([42]Tutte′s Theorem) A graphG=(V,E) has a perfect matching if and only ifo(G-S) ≤|S| for allS⊆V.

Claim1BSn-F1-F2does not contain isolated vertex.

Since |F1|≤8n-20, |F2|≤8n-20 and |F1∩F2|≥8n-23, we have |F2F1|=|F2|-|F1∩F2|≤8n-20-(8n-23)=3 and |F1F2|≤3.

Case1|F2F1|=3.

In this case, |F1∩F2|= 8n-23. By Theorem 5,F1∩F2is a minimum 3-extra cut ofBSn. By Theorem 6,BSnis tightly (8n-23) super 3-extra connected, i.e.,BSn-(F1∩F2) has two components, one of which is a connected subgraph of order 4. Since every componentGiofBSn[(F2∩F1)∪W] has |V(Gi)|≥5, we have that |V(BSn-F1-F2)|=4. By Lemma 3, |W|≤o(G-(F1∪F2))≤|F1∪F2|≤|F1|+|F2|≤8n-20+8n-20=16n-40. Thus,n!=|V(BSn)|=|V(BSn-F1-F2)|+ |F2F1|+|F1F2|+|W|+|F2∩F1|≤4+3+3+16n-40+8n-23=24n-53, a contradiction ton≥5.

Case2|F2F1|=2.

Letx,y∈F2F1. Supposexy∉E(BSn). SinceF1is a 3-extra set ofBSn, we have that every componentBiofBSn[W∪(F2F1)]) has |V(Bi)|≥4. Suppose thatx,y∈V(Bi). Then there is anxy-path inBi. It’s only possible that there are edges between {x,y} andWinBSn[W∪(F2F1)]). Therefore, thexy-path is thexwy, wherew∈W. This contradicts the fact that there is just a vertex ofF2F1such that it is adjacent to a vertex ofW. Therefore,BSn[W∪(F2F1)]) has two componentsB1andB2such thatx∈V(B1) andy∈V(B2). Since |V(B1)|≥4, |W|≥3. Since every vertex ofWis adjacent to just a vertex ofF2F1and |V(B2)|≥4, we have that |W|≥6. If |F1F2|= 3, then |F1∩F2|=8n-23, a contradiction. Therefore, 1≤|F1F2|≤2. If |F1F2|=1, then, by Proposition 5, |W|=6. Let {z}=F1F2. We have that |N({x,y})∩(F1∩F2)|+ |N(z)∩(F1∩F2)|+|N(W)((F2F1)∪(F1F2))|≥2(2n-6)+2n-9+6(2n-5)-24=18n-75> 8n-22 whenn≥6, a contradiction to |F1∩F2|=8n-22. LetF1F2={u,v}. Suppose thatuv∉E(BSn).

By Proposition 5, |N(x)∩N(u)∩W|≤3 and |N(x)∩N(v)∩W|≤3. Since every vertex ofWis adjacent to just a vertex ofF1F2, |(N(x)∩N(u)∩W)∪(N(x)∩N(v)∩W)|=|(N(x)∩N(u)∩W)|+ |(N(x)∩N(v)∩W)|. SinceF2is a 3-extra set ofBSn, |N(u)∩W|≥3 and |N(v)∩W|≥3. Therefore, |(N(x)∩N(u)∩W)∪(N(x)∩N(v)∩W)|=|(N(x)∩N(u)∩W)|+|(N(x)∩N(v)∩W)|≤6. Similarly, |(N(y)∩N(u)∩W)∪(N(y)∩N(v)∩W)|=|(N(y)∩N(u)∩W)|+|(N(y)∩N(v)∩W)|≤6. Since (N(x)∩W)∩(N(y)∩W)=∅, 6≤|(N({x,y,u,v})∩W|≤12.

Casea1N({u})∩W≠∅ andN({v})∩W=∅.

By Proposition 5, |N(x)∩N(u)∩W|≤3 and |N(y)∩N(u)∩W|≤3. Since every vertex inWis adjacent touinBSn[W∪(F1F2)], |W|=6. From the above discussion, there is a contradiction.

Casea2N({u})∩W≠∅ andN({v})∩W≠∅.

By Proposition 5, |N(x)∩N(u)∩W|≤3 and |N(x)∩N(v)∩W|≤3. If |N(x)∩N(u)∩W|≠0, then, by Proposition 4, |N(x)∩N(v)∩W|=0. Let |N(x)∩N(u)∩W|≠0. Then |N(x)∩N(v)∩W|=0. Since every vertex ofWis adjacent to just a vertex ofF1F2, |N(x)∩N(u)∩W|=3.

SinceN({v})∩W≠∅, 1≤|N(y)∩N(v)∩W|≤3. Note that |N(y)∩N(u)∩W|=0 and every vertex ofWis adjacent to just a vertex ofF1F2. Therefore, |N(y)∩N(v)∩W|=3 and |W|=6. From the above discussion, there is a contradiction.

Supposexy∈E(BSn). From the above discussion, 1≤|F1F2|≤2. We consider the following subcases.

Caseb1N({x})∩W≠∅ andN({y})∩W=∅.

Let |F1F2|=1 and {u}=F1F2. SinceF1is a 3-extra set ofBSn, |N(x)∩W|≥2. By Proposition 5, |N(x)∩N(u)∩W|≤3. SinceF2is a 3-extra set ofBSn, |N(u)∩W|≥3. Therefore, |W|= 3. We have that |N({x,y,u})∩(F1∩F2)|+|N(W)((F2F1)∪(F1F2))|≥3(2n-5)+(2n-4)+(2n-7)+(2n-6)-9=14n-41> 8n-22 whenn≥4, a contradiction to |F1∩F2|=8n-22.Let |F1F2|=2 and {u,v}=F1F2.

Suppose thatuv∉E(BSn). By Case a1, there is a contradiction.

Suppose thatuv∈E(BSn). Recall that |N(x)∩W|≥2. IfN({u})∩W≠∅ andN({v})∩W≠∅, then there is a 5-cycle, a contradiction to Proposition 4. IfN({u})∩W≠∅ andN({v})∩W=∅, then 2≤|W|≤3. Similarly to above, there is a contradiction.

Caseb2N({x})∩W≠∅ andN({y})∩W≠∅.

Let |F1F2|=1 and {u}=F1F2. Since every vertex ofWis adjacent to just a vertex ofF2F1, (N({x})∩W)∩(N({y})∩W)=∅. Forw1∈N({x})∩Wandw2∈N({y})∩W,w1u,w2u∈E(BSn) and hencexw1uw2yxis a 5-cycle, a contradiction to Proposition 4. Let |F1F2|=2 and {u,v}=F1F2.

Suppose thatuv∉E(BSn). By Case a2, there is a contradiction. Suppose thatuv∈E(BSn).

By Proposition 5, |N(x)∩N(u)∩W|≤3 and |N(x)∩N(v)∩W|≤3. IfN(x)∩N(u)∩W≠∅ andN(x)∩N(v)∩W≠∅, then there is a 5-cycle, a contradiction. LetN(x)∩N(u)∩W≠∅. Then |N(x)∩N(u)∩W|≤3. Similarly, |N(y)∩N(3)∩W|≤3. Therefore, 2≤|W|≤6. Similarly to above, there is a a contradiction.

Case3|F2F1|=1.

Case3.1|F1∩F2|=8n-23.

Similarly to above, there is a contradiction.

Case3.2|F1∩F2|=8n-22.

Since |F1|≤8n-20, 1≤|F1F2|≤2. When |F1F2|= 2, we discuss in Case 2. Let |F1F2|=1. Letx∈F2F1. SinceF1is a 3-extra set ofBSn, we have that every componentBiofBSn[W∪(F2F1)]) has |V(Bi)|≥4. Sincex∈F2F1,BSn[W∪(F2F1)]) has a componentB1. Letx∈V(B1). Since |V(B1)|≥4, |W|≥3 and there area,b,c∈Wsuch thatxa,xb,xc∈E(BSn). Lety∈F1F2. SinceF2is a 3-extra set ofBSn,ya,yb,yc∈E(BSn) and |W|=3. Therefore, |F2∩F1|≥3(2n-5)+2(2n-6)-3=10n-30>8n-22=|F1∩F2|, a contradiction ton≥7.

Case3.3|F1∩F2|=8n-21.

In this case, |F1F2|=|F2F1|=1. We discuss it in Case 3.2. Claim 1 is complete.

Letu∈V(BSn-F1-F2). Thenuis adjacent toBSn-F1-F2from Claim 1. Since (F1,F2) can not be applied in Theorem 9, according to the condition (1) in Theorem 9, adjacent verticesu,w∈V(BSn-F1-F2) does not satisfyuw∈E(BSn) andvw∈E(BSn) wherev∈F1ΔF2. We deduce thatuis not adjacent to any vertex of (F1F2)∪(F2F1). According to the generality ofu,V(BSn-F1-F2) is not connected toF1ΔF2.

Combining Lemma 2 and Lemma 4, we have the following theorem.

Theorem10Letn≥12. Then the 3-extra diagnosability of the bubble-sort star graphBSnunder the MM*model is 8n-20.

4 Conclusions

In this paper, we investigate the problem of the 3-extra diagnosability of the bubble-sort star graphBSnunder the PMC model and the MM*model. It is proved that 3-extra diagnosability ofBSnis 8n-20 under the PMC model forn≥5 and under the MM*model forn≥12. The above results show that the 3-extra diagnosability is several times larger than the classical diagnosability ofBSndepending on the condition: 3-extra. The work will help engineers to develop more different measures of 3-extra diagnosability based on application environment, network topology, network reliability, and statistics related to fault patterns.