中文

Operations Research Transactions >

2019 , Vol. 23 >Issue 1: 97 - 103

DOI: https://doi.org/10.15960/j.cnki.issn.1007-6093.2019.01.011

The 1-good-neighbor diagnosability of the Cayley graphs UGn generated by unicyclic graphs under the PMC model and the MM* model

Expand
  • 1. College of Mathematics, Inner Mongolia University for Nationalities, Tongliao 028043, Inner Mongolia Autonomous Region, China;
    2. College of Computer Science and Technology, Inner Mongolia University for Nationalities, Tongliao 028043, Inner Mongolia Autonomous Region, China;
    3. School of Mathematics and Information Science, Henan Normal University, Xinxiang 453007, Henan, China

Received date: 2017-09-11

  Online published: 2019-03-15

Fold

Abstract

Diagnosability of a multiprocessor system is an important study topic. A new measure for fault diagnosis of the system is called g-good-neighbor diagnosability that restrains every fault-free node containing at least g fault-free neighbors. As a famous topology structure of interconnection networks, the Cayley graph UGn generated by unicyclic graphs has many good properties. In this paper, we prove that the 1-good-neighbor diagnosability of the Cayley graph UGn generated by unicyclic graphs is 2n-1 under the PMC model for n ≥ 4; the 1-good-neighbor diagnosability of the Cayley graph UGn generated by unicyclic graphs is 2n-1 under the MM* model for n ≥ 5.

Key words： interconnection network; diagnosability; Cayley graph; PMC model; MM* model

Cite this article

REN Jiamin, FENG Wei, ZHAO Lingqi, WANG Shiying, JIRIMUTU . The 1-good-neighbor diagnosability of the Cayley graphs UGn generated by unicyclic graphs under the PMC model and the MM* model[J]. Operations Research Transactions, 2019 , 23(1) : 97 -103 . DOI: 10.15960/j.cnki.issn.1007-6093.2019.01.011

References

[1] Preparata F, Metze G, Chien R T. On the connection assignmemt problem of diagnosable systems[J]. IEEE Transactions on Electronic Computers, 1968, 12:848-854.
[2] Joon M, Miroslaw M. A comparision connection assignment for self-Diagnosis of multiprocessor systems[J]. Proceeding of 11th International Symposium on Fault-Tolerant Computing, 1981, 173-175.
[3] Lai P L, Tan J J M, Chang C P, et al. Conditional diagnosability measures for large multiprocessor systems[J]. IEEE Transactions on Computers, 2005, 54:165-175.
[4] Peng S L, Lin C K, Tan J J M, et al. The g-good-neighbor conditional diagnosability of hypercube under the PMC model[J]. Applied Mathematics Computation, 2012, 218:10406-10412.
[5] Wang S Y, Han W P. The g-good-neighbor conditional diagnosability of n-dimensional hypercubes under the MM* model[J]. Information Processing Letters, 2016, 116:574-577.
[6] Yuan J, Liu A X, Ma X, et al. The g-good-neighbor conditional diagnosability of k-ary n-cubes under the PMC model and MM* model[J]. IEEE Transactions on Parallel and Distributed Systems, 2015, 26:1165-1177.
[7] Wang M J J, Guo Y B, Wang S Y. The 1-good-neighbor diagnosability of Cayley graphs generated by transposition trees under the PMC model and MM* model[J]. International Journal of Computer Mathematics, 2015, 23:1-12.
[8] Ma X L, Wang S Y, Wang Z H. The 1-good-neighbor connectivity and diagnosability of crossed cubes[J]. 应用数学进展, 2016, 5:282-290.
[9] Bai C, Wang S Y, Wang Z H. The 1-good-neighbor connectivity and diagnosability of Möbius cubes[J]. 应用数学进展, 2016, 5:728-737.
[10] Bondy J A, Murty U S R. Graph Theory[M]. New York:Springer, 2007.
[11] Song C Y, Huang Q X. The nullity of unicyclic graphs[J]. 运筹学学报, 2009, 13:77-83.
[12] Yu X M, Zhang Z. A kind of conditional connectivity of Cayley graphs generated by unicyclic graphs[J]. Information Science, 2013, 243:86-94.
[13] Cheng E, LiptSk L. Fault resiliency of Cayley graphs generated by transpositions[J]. International Journal of Foundations of Computer Science, 2007, 18:1005-1022.

Options
Outlines

/

〈 〉