A Note on the Nature Diagnosability of Alternating Group Graphs Under the PMC Model and MM* Model

作者：SHIYING, WANG; LINGQI, ZHAO

来源：Journal of Interconnection Networks, 2018, 18(01): 1850005.

DOI：10.1142/s0219265918500056

<jats:p> Many multiprocessor systems have interconnection networks as underlying topologies and an interconnection network is usually represented by a graph where nodes represent processors and links represent communication links between processors. No faulty set can contain all the neighbors of any fault-free node in the system, which is called the nature diagnosability of the system. Diagnosability of a multiprocessor system is one important study topic. As a favorable topology structure of interconnection networks, the n-dimensional alternating group graph AG<jats:sub>n</jats:sub> has many good properties. In this paper, we prove the following. (1) The nature diagnosability of AG<jats:sub>n</jats:sub> is 4n − 10 for n − 5 under the PMC model and MM<jats:sup>*</jats:sup> model. (2) The nature diagnosability of the 4-dimensional alternating group graph AG4 under the PMC model is 5. (3) The nature diagnosability of AG<jats:sub>4</jats:sub> under the MM<jats:sup>*</jats:sup> model is 4. </jats:p>

• 出版日期2018-3
• 单位内蒙古大学