American Journal of Computational Mathematics
Vol.09 No.03(2019), Article ID:94584,10 pages
10.4236/ajcm.2019.93010
A Proof for g-Good-Neighbor Diagnosability of Exchanged Hypercubes
Yunxia Ren, Shiying Wang
School of Mathematics and Information Science, Henan Normal University, Xinxiang, China
Copyright © 2019 by author(s) and Scientific Research Publishing Inc.
This work is licensed under the Creative Commons Attribution International License (CC BY 4.0).
http://creativecommons.org/licenses/by/4.0/
Received: June 24, 2019; Accepted: August 23, 2019; Published: August 26, 2019
ABSTRACT
The diagnosability of a multiprocessor system or an interconnection network is an important research topic. The system and an interconnection network have an underlying topology, which is usually presented by a graph. In this paper, we show proof for the g-good-neighbor diagnosability of the exchanged hypercube under the PMC model and MM* model.
Keywords:
Interconnection Network, Diagnosability, Exchanged Hypercube
1. Introduction
A multiprocessor system and interconnection network have an underlying topology, which is usually presented by a graph, where nodes represent processors and links represent communication links between processors. Some processors may fail in the system and processor fault identification plays an important role in reliable computing. The identification process is called the diagnosis of the system. Several diagnosis models were proposed to identify the faulty processors. One major approach is the Preparata, Metze, and Chien’s (PMC) diagnosis model introduced by Preparata et al. [1] . Under the PMC model, the diagnosis of the system is achieved through two linked processors testing each other. Another major approach, namely, the comparison diagnosis model (MM model), was proposed by Maeng and Malek [2] . Under the MM model, to diagnose a system, a node sends the same task to two of its neighbors, and then compares their responses. The MM* is a special case of the MM model and each node must test all pairs of its adjacent nodes of the system. The diagnosability of the system is one important study topic. In 2012, Peng et al. [3] proposed measurement for fault diagnosis of the system, namely, the g-good-neighbor diagnosability (which is also called the g-good-neighbor conditional diagnosability), which requires that every fault-free node has at least g fault-free neighbors. Numerous studies have been investigated under the PMC and the MM model or the MM* model, see [2] - [23] .
Let be the exchanged hypercube with . In this paper, we show the following: 1) The g-good-neighbor diagnosability of is under the PMC model for any g with . 2) The diagnosability of under the MM* model is for . 3) The g-good-neighbor diagnosability of under the MM* model is for and any g with .
The rest of this paper is organized as follows: In Section 2, we provide the terminology and preliminaries for the system diagnosis. In Section 3, we shall show the g-good-neighbor diagnosability of the exchanged hypercube under the PMC model and the MM* model. Finally, the conclusion is given in Section 4.
2. Preliminaries
A multiprocessor system and a network are modeled as an undirected simple graph , denotes processors and denotes communication links. For with , the subgraph of G induced by , denoted by . For with , the symmetric difference is . For , the neighborhood of v in G to be the set of vertices adjacent to v. Let . The set is denoted by . For graph-theoretical terminology and notation not defined here we follow [24] .
Let be connected. A fault set is called a g-good-neighbor faulty set if for every vertex v in . A g-good-neighbor cut of G is a g-good-neighbor faulty set F such that is disconnected. The minimum cardinality of g-good-neighbor cuts is said to be the g-good-neighbor connectivity of G, denoted by . A connected graph G is said to be g-good-neighbor connected if G has a g-good-neighbor cut.
Definition 2.1. A system is g-good-neighbor t-diagnosable under the PMC model if and only if is distinguishable for each distinct pair of g-good-neighbor faulty subsets and of V with and . The g-good-neighbor diagnosability of G is the maximum value of t such that G is g-good-neighbor t-diagnosable under the PMC model. In particular, is said to be the diagnosability of G under the PMC model, is said to be the nature diagnosability of G under the PMC model.
Definition 2.2. A system is g-good-neighbor t-diagnosable under the MM* model if and only if is distinguishable for each distinct pair of g-good-neighbor faulty subsets and of V with and . The g-good-neighbor diagnosability of G is the maximum value of t such that G is g-good-neighbor t-diagnosable under the MM* model. In particular, is said to be the diagnosability of G under the MM* model, is said to be the nature diagnosability of G under the MM* model.
For a given position integer n, let . The sequence is called a binary string of length n if for each . Let and be two distinct binary strings of length n.
Hamming distance between x and y, denoted by , is the number of r’s for which for .
For a binary string of length , we call the r-th bit of u for , and the last bit of u, denote sub-sequence of u by , i.e., . Let .
Definition 2.3. The exchanged hypercube is an undirected graph , where and are integers. The set of vertices V is , and the set of edges E is composed of three disjoint types , and : ,,.
3. The g-Good-Neighbor Diagnosability of the Exchanged Hypercube under the PMC and the MM* Model
Theorem 3.1. [9] For and any g with ,.
Let and let . Then . By the proof of Lemma 3.1 in [9] , we have the following.
Lemma 3.2. Let be the exchanged hypercube with . is defined as above for . Then ,, and is a g-good-neighbor cut of .
Theorem 3.3. [19] Let be a g-good-neighbor connected graph, and let H be connected subgraph of G with such that it contains as least as possible and is a minimum g-good-neighbor cut of G, and let be connected subgraph of G with such that it contains as least as possible. If for each distinct pair of g-good-neighbor faulty subsets and of G with and , then under the PMC model.
Theorem 3.4. Let be the exchanged hypercube with and any g with . Then the g-good-neighbor diagnosability of is under the PMC model.
Proof. Let be defined in Lemma 3.2 for . By the definition of , is minimum such that . Note . Therefore, for each distinct pair of g-good-neighbor faulty subsets and of with and . By Theorem 3.4, . On the other hand, by Lemma 3.2, is a g-good-neighbor cut of . Since , by Theorem 3.1, is a minimum g-good-neighbor cut of . Note . By Theorem 3.4, . Therefore, . ,
Before discussing the g-good-neighbor diagnosability of the exchanged hypercube under the MM* model, we first give two existing results.
Theorem 3.5. [4] [21] A system is g-good-neighbor t-diagnosable under the MM* model if and only if for each distinct pair of g-good-neighbor faulty subsets and of V with and satisfies one of the following conditions. 1) There are two vertices and there is a vertex such that and . 2) There are two vertices and there is a vertex such that and . 3) There are two vertices and there is a vertex such that and .
Theorem 3.6. [19] Let be a g-good-neighbor connected graph, and let H be connected subgraph of G with such that it contains as least as possible, and is a minimum g-good-neighbor cut of G. Then the g-good-neighbor diagnosability of G is less than or equal to , i.e., under the PMC model and MM* model.
Lemma 3.7. Let be the exchanged hypercube with and any g with . Then the g-good-neighbor diagnosability of the exchanged hypercube under the MM* model is less than or equal to , i.e., .
Proof. Let be defined in Lemma 3.2 for . By the definition of , is minimum such that . By Lemma 3.2, is a g-good-neighbor cut of . By Theorems 3.6 and 3.1, . ,
A component of a graph G is odd according as it has an odd number of vertices. We denote by the number of odd component of G.
Lemma 3.8. [24] A graph has a perfect matching if and only if for all .
Lemma 3.9. [8] Let G be a graph representation of a system. Then the diagnosability under the MM* model.
Theorem 3.10. Let be the exchanged hypercube with . Then the 0-good-neighbor diagnosability of under the MM* model is , i.e., .
Proof. By the definition of the g-good-neighbor diagnosability, it is sufficient to show that is 0-good-neighbor -diagnosable.
By Theorem 3.5, suppose, on the contrary, that there are two distinct 0-good-neighbor faulty subsets and of with and , but the vertex set pair is not satisfied with any one condition in Theorem 3.5. Without loss of generality, assume that . Note . Therefore, .
Note has a perfect matching. Let be the set of isolated vertices in , and let H be the subgraph induced by the vertex set . By Lemma 3.8, . Note . Therefore, . Since and are two distinct 0-good-neighbor faulty sets, and there is no edge between and , we have that is a 0-good-neighbor cut of . By Theorem 3.1, we have . Therefore, , which contradicts . Therefore, is 0-good-neighbor -diagnosable and . Combining this with Lemma 3.9, we have . ,
Theorem 3.11. Let be the exchanged hypercube with . Then the 1-good-neighbor diagnosability of under the MM* model is , i.e., .
Proof. By the definition of 1-good-neighbor diagnosability, it is sufficient to show that is 1-good-neighbor -diagnosable.
By Theorem 3.5, suppose, on the contrary, that there are two distinct 1-good-neighbor faulty subsets and of with and , but the vertex set pair is not satisfied with any one condition in Theorem 3.5. Without loss of generality, assume that . Note . Therefore, .
Claim I. has no isolated vertex.
Suppose, on the contrary, that has at least one isolated vertex w. Since is a 1-good neighbor faulty set, there is a vertex such that u is adjacent to w. Since the vertex set pair is not satisfied with any one condition in Theorem 3.5, there is at most one vertex such that u is adjacent to w. Thus, there is just a vertex such that u is adjacent to w. If , then . Since is a 1-good neighbor faulty set, has not any isolated vertex; a contradiction. Therefore, . Similarly, we can deduce that there is just a vertex such that v is adjacent to w. Let be the set of isolated vertices in , and let H be the subgraph induced by the vertex set . Then for any , there are neighbors in . Note has a perfect matching. By Lemma 3.8, . Suppose . Then . This is a contradiction to . So . Since the vertex set pair is not satisfied with the condition (1) of Theorem 3.5, and any vertex of is not isolated in H, we induce that there is no edge between and . Thus, is a vertex cut of and , i.e., is a 1-good-neighbor cut of . By Theorem 3.1, . Because ,, and neither nor is empty, we have and . Let and . Then for any vertex , w are adjacent to and . Note that there are at most two common neighbors for any pair of vertices in , it follows that there are at most two isolated vertices in .
Suppose that there is exactly one isolated vertex v in . Let and be adjacent to v. Then . Since contains no triangle, it follows that ; ; , and .
Thus, . It follows that , which contradicts .
Suppose that there are exactly two isolated vertices v and w in . Let and be adjacent to v and w, respectively. Then . Since contains no triangle, it follows that ,,, and .
Thus, . It follows that , which contradicts . The proof of Claim I is complete.
Let . By Claim I, u has at least one neighbor in . Since the vertex set pair is not satisfied with any one condition in Theorem 3.5, by the condition (1) of Theorem 3.5, for any pair of adjacent vertices , there is no vertex such that and . It follows that u has no neighbor in . By the arbitrariness of u, there is no edge between and . Since and is a 1-good-neighbor faulty set, . Note . Since both and are 1-good-neighbor faulty sets, and there is no edge between and , is a 1-good-neighbor cut of . By Theorem 3.1, . Therefore, , which contradicts . Therefore, is 1-good-neighbor -diagnosable and . Combining this with Lemma 3.7, we have . ,
Theorem 3.12. Let be the exchanged hypercube with and any g with . Then the g-good-neighbor diagnosability of the exchanged hypercube under the MM* model is , i.e., .
Proof. By the definition of the -good-neighbor diagnosability, it is sufficient to show that is g-good-neighbor -diagnosable. By Theorems 3.10 and 3.11, it is sufficient to show that .
By Theorem 3.5, suppose, on the contrary, that there are two distinct g-good-neighbor faulty subsets and of with and , but the vertex set pair is not satisfied with any one condition in Theorem 3.5. Without loss of generality, assume that . It is easy to verify . Therefore, .
Claim 1. has no isolated vertex.
Suppose, on the contrary, that has at least one isolated vertex x. Since is a g-good neighbor faulty set and , there are at least two vertices such that are adjacent to x. According to the hypothesis, the vertex set pair is not satisfied with any one condition in Theorem 3.5. By the condition (3) of Theorem 3.5, there are at most one vertex such that u are adjacent to x. So , a contradiction to that is a g-good neighbor faulty set, where . Thus, has no isolated vertex.
The proof of Claim 1 is complete.
Let . By Claim 1, . Since the vertex set pair is not satisfied with any one condition in Theorem 3.5, by the condition (1) of Theorem 3.5, for any pair of adjacent vertices , there is no vertex such that and . It follows that u has no neighbor in . By the arbitrariness of u, there is no edge between and . Since and is a g-good-neighbor faulty set, and . By the definition of ,. Since both and are g-good-neighbor faulty sets, and there is no edge between and , is a g-good-neighbor cut of . By Theorem 3.1, . Therefore, , which contradicts . Therefore, is g-good-neighbor -diagnosable and . Combining this with Lemma 3.7, we have . ,
4. Conclusion
In this paper, we investigate the problem of the diagnosability of the exchanged hypercube . We show the following. Let be the exchanged hypercube with and any g with . Then the g-good-neighbor diagnosability of under the PMC model and MM* model is . The work will help engineers to develop more different measures of the diagnosability based on application environment, network topology, network reliability, and statistics related to fault patterns.
Acknowledgements
This work is supported by the National Natural Science Foundation of China (61772010) and the Science Foundation of Henan Normal University (Xiao 20180529, 20180454).
Conflicts of Interest
The authors declare no conflicts of interest regarding the publication of this paper.
Cite this paper
Ren, Y.X. and Wang, S.Y. (2019) A Proof for g-Good-Neighbor Diagnosability of Exchanged Hypercubes. American Journal of Computational Mathematics, 9, 133-142. https://doi.org/10.4236/ajcm.2019.93010
References
- 1. Preparata, F.P., Metze, G. and Chien, R.T. (1967) On the Connection Assignment Problem of Diagnosable Systems. IEEE Transactions on Computers, EC-16, 848-854. https://doi.org/10.1109/PGEC.1967.264748
- 2. Maeng, J. and Malek, M. (1981) A Comparison Connection Assignment for Self-Diagnosis of Multiprocessor Systems. Proceeding of 11th International Symposium on Fault-Tolerant Computing, Portland, 24-26 June 1981, 173-175.
- 3. Peng, S.-L., Lin, C.-K., Tan, J.J.M. and Hsu, L.-H. (2012) The g-Good-Neighbor Conditional Diagnosability of Hypercube under PMC Model. Applied Mathematics and Computation, 218, 10406-10412. https://doi.org/10.1016/j.amc.2012.03.092
- 4. Dahbura, A.T. and Masson, G.M. (1984) An Fault Identification Algorithm for Diagnosable Systems. IEEE Transactions on Computers, C-33, 486-492. https://doi.org/10.1109/TC.1984.1676472
- 5. Fan, J. (2002) Diagnosability of Crossed Cubes under the Comparison Diagnosis Model. IEEE Transactions on Parallel and Distributed Systems, 13, 1099-1104. https://doi.org/10.1109/TPDS.2002.1041887
- 6. Hsieh, S.Y. and Kao, C.Y. (2013) The Conditional Diagnosability of k-Ary n-Cubes under the Comparison Diagnosis Model. IEEE Transactions on Computers, 62, 839-843. https://doi.org/10.1109/TC.2012.18
- 7. Lai, P.-L., Tan, J.J.M., Chang, C.-P. and Hsu, L.-H. (2005) Conditional Diagnosability Measures for Large Multiprocessor Systems. IEEE Transactions on Computers, 54, 165-175. https://doi.org/10.1109/TC.2005.19
- 8. Lee, C.-W. and Hsieh, S.-Y. (2013) Diagnosability of Multiprocessor Systems, in: Scalable Computing and Communications: Theory and Practice, Wiley, New York.
- 9. Li, X.-J. and Xu, J.-M. (2013) Generalized Measures of Fault Tolerance in Exchanged Hypercubes. Information Processing Letters, 113, 533-537.
- 10. Ren, Y. and Wang, S. (2017) The g-Good-Neighbor Diagnosability of Locally Twisted Cubes. Theoretical Computer Science, 697, 91-97.
- 11. Wang, M., Guo, Y. and Wang, S. (2017) The 1-Good-Neighbor Diagnosability of Cayley Graphs Generated by Transposition Trees under the PMC Model and MM* Model. International Journal of Computer Mathematics, 94, 620-631. https://doi.org/10.1080/00207160.2015.1119817
- 12. Wang, M., Lin, Y. and Wang, S. (2016) The 2-Good-Neighbor Diagnosability of Cayley Graphs Generated by Transposition Trees under the PMC Model and MM* Model. Theoretical Computer Science, 628, 92-100.
- 13. Wang, M. Lin, Y. and Wang, S. (2018) The 1-Good-Neighbor Connectivity and Diagnosability of Cayley Graphs Generated by Complete Graphs. Discrete Applied Mathematics, 246, 108-118.
- 14. Wang, S. and Han, W. (2016) The g-Good-Neighbor Conditional Diagnosability of n-Dimensional Hypercubes under the MM* Model. Information Processing Letters, 116, 574-577.
- 15. Wang, S., Wang, Z., Wang, M. and Han, W. (2017) The g-Good-Neighbor Conditional Diagnosability of Star Graph Networks under the PMC Model and MM* mode. Frontiers of Mathematics in China, 12, 1221-1234. https://doi.org/10.1007/s11464-017-0657-9
- 16. Wang, S., Wang, Z. and Wang, M. (2017) The 2-Good-Neighbor Connectivity and 2-Good-Neighbor Diagnosability of Bubble-Sort Star Graph Networks. Discrete Applied Mathematics, 217, 691-706.
- 17. Wang, S. and Yang, Y. (2017) The 2-Good-Neighbor (2-Extra) Diagnosability of Alternating Group Graph Networks under the PMC Model and MM* Model. Applied Mathematics and Computation, 305, 241-250.
- 18. Wang, S. and Ma, X. (2018) The g-Extra Connectivity and Diagnosability of Crossed Cubes. Applied Mathematics and Computation, 336, 60-66. https://doi.org/10.1016/j.amc.2018.04.054
- 19. Wang, S. and Wang, M. (2019) The g-Good-Neighbor and g-Extra Diagnosability of Networks. Theoretical Computer Science, 773, 107-114. https://doi.org/10.1016/j.tcs.2018.09.002
- 20. Xu, X., Zhou, S. and Li, J. (2017) Reliability of Complete Cubic Networks under the Condition of g-Good-Neighbor. The Computer Journal, 60, 625-635. https://doi.org/10.1093/comjnl/bxw078
- 21. Yuan, J., Liu, A., Ma, X., Liu, X., Qin, X. and Zhang, J. (2015) The g-Good-Neighbor Conditional Diagnosability of k-Aryn-Cubes under the PMC Model and MM* Model. IEEE Transactions on Parallel and Distributed Systems, 26, 1165-1177. https://doi.org/10.1109/TPDS.2014.2318305
- 22. Yuan, J., Liu, A., Qin, X., Zhang, J. and Li, J. (2016) g-Good-Neighbor Conditional Diagnosability Measures for 3-Ary n-Cube Networks. Theoretical Computer Science, 622, 144-162. https://doi.org/10.1016/j.tcs.2016.01.046
- 23. Zheng, J., Latifi, S., Regentova, E., Luo, K. and Wu, X. (2005) Diagnosability of Star Graphs under the Comparison Diagnosis Model. Information Processing Letters, 93, 29-36. https://doi.org/10.1016/j.ipl.2004.09.011
- 24. Bondy, J.A. and Murty, U.S.R. (2007) Graph Theory. Springer, New York.