单圈图生成的凯莱图UGn在PMC模型和MM*模型下的1好邻诊断度

doi:10.15960/j.cnki.issn.1007-6093.2019.01.011

Operations Research Transactions ›› 2019, Vol. 23 ›› Issue (1): 97-103.doi: 10.15960/j.cnki.issn.1007-6093.2019.01.011

Previous Articles Next Articles

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

REN Jiamin¹, FENG Wei¹, ZHAO Lingqi², WANG Shiying³, JIRIMUTU^1,*

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:2017-09-11 Online:2019-03-15 Published:2019-03-15

Abstract

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 UG_n generated by unicyclic graphs has many good properties. In this paper, we prove that the 1-good-neighbor diagnosability of the Cayley graph UG_n generated by unicyclic graphs is 2n-1 under the PMC model for n ≥ 4; the 1-good-neighbor diagnosability of the Cayley graph UG_n 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

CLC Number:

O157.5

REN Jiamin, FENG Wei, ZHAO Lingqi, WANG Shiying, JIRIMUTU. The 1-good-neighbor diagnosability of the Cayley graphs UG_n generated by unicyclic graphs under the PMC model and the MM^* model[J]. Operations Research Transactions, 2019, 23(1): 97-103.

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.

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

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 3

Recommended Articles

Metrics

Comments

[1]	SONG Sulin, LIN Limei, ZHOU Shuming. The t/k-diagnosability and diagnosis algorithm of Pancake networks [J]. Operations Research Transactions, 2014, 18(4): 65-77.
[2]	WANG Guoliang, SHI Haizhong. The restricted connectivity of complete-transposition networks [J]. Operations Research Transactions, 2013, 17(3): 57-64.
[3]	SHI Hai-Zhong, NIU Pan-Feng, MA Ji-Yong, HOU Fei-Fei. A vector graph model for interconnection networks [J]. Operations Research Transactions, 2011, 15(3): 115-123.

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

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 3

Recommended Articles

Metrics

Comments

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