English

运筹学学报 >

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

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

运筹学

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

展开
  • 1. 内蒙古民族大学数学学院, 内蒙古通辽 028043;
    2. 内蒙古民族大学计算机科学与技术学院, 内蒙古通辽 028043;
    3. 河南师范大学数学与信息科学学院, 河南新乡 453007

收稿日期: 2017-09-11

  网络出版日期: 2019-03-15

基金资助

国家自然科学基金（Nos.61262018，61370001，61402317），内蒙古民族大学科学研究项目（No.NMDGP17106）

收起

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

摘要

多处理系统的诊断度是一个重要的研究课题.一种新的系统故障诊断方法称为g好邻诊断度，它是限制每个无故障点至少包含g个无故障的邻点.单圈图生成的凯莱图UGn作为一种极好的互联网络拓扑结构有许多好的性质.现证明了当n ≥ 4时，单圈图生成的凯莱图UGn在PMC模型下的1好邻诊断度是2n-1；当n ≥ 5时，UGn在MM*模型下的1好邻诊断度是2n-1.

关键词： 互联网络; 诊断度; 凯莱图; PMC模型; MM*模型

本文引用格式

任佳敏, 冯伟, 赵凌琪, 王世英, 吉日木图 . 单圈图生成的凯莱图UGn在PMC模型和MM*模型下的1好邻诊断度[J]. 运筹学学报, 2019 , 23(1) : 97 -103 . DOI: 10.15960/j.cnki.issn.1007-6093.2019.01.011

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

参考文献

[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
文章导航

/

〈 〉