无K_3子图的互连网络在PMC模型下的条件可诊断度

Conditional diagnosability of K_3-free graph under PMC model

可诊断度是衡量一个互连网络可靠性的重要指标,常用来评估当系统中某些节点出现故障时将故障节点准确找出来的能力。PMC模型是一种经典的可诊断模型,被广泛地应用于系统诊断中,到目前为止,已经有很多的研究者基于PMC模型作出了大量研究成果。在PMC模型的基础上,对于不存在K_3子图的网络条件可诊断性进行了研究,并证明了当δ(G)≥9且任两个节点的共同邻居数不大于2时,无K_3子图的图G是2δ(G)-1条件可诊断的;当δ(G)≥6且任两个节点的共同邻居数不大于2时,二部图G是2δ(G)-1条件可诊断的。

The diagnosability is an important standard to judge the reliability of the interconnection network, in order to evaluate the capacity of a system to find the fauit nodes. The PMC model is a classical diagnostic model which has applied to sys- tem diagnosis widely. There are many researches under the PMC model have been proposed. This paper studied the conditional diagnosability of K3-free graphs under the PMC model. And it proved that when the number of eommom neighbors of any 2 nodes is not more than 2 with 8（G） 1〉9, then the conditional diagnosability of K3-free graph is 28（G） - 1. The paper also proves that when the number of commom neighbors of any 2 nodes is not more than 2 with 8（G） ≥6, the conditional diagnos- ability of bipartite graph is 28（G） - 1.