تقرير
Equal relation between the extra connectivity and pessimistic diagnosability for some regular graphs
| العنوان: | Equal relation between the extra connectivity and pessimistic diagnosability for some regular graphs |
|---|---|
| المؤلفون: | Gu, Mei-Mei, Hao, Rong-Xia, Xu, Jun-Ming, Feng, Yan-Quan |
| سنة النشر: | 2017 |
| المجموعة: | Mathematics |
| مصطلحات موضوعية: | Mathematics - Combinatorics, 68R10, G.2.2 |
| الوصف: | Extra connectivity and the pessimistic diagnosis are two crucial subjects for a multiprocessor system's ability to tolerate and diagnose faulty processor. The pessimistic diagnosis strategy is a classic strategy based on the PMC model in which isolates all faulty vertices within a set containing at most one fault-free vertex. In this paper, the result that the pessimistic diagnosability $t_p(G)$ equals the extra connectivity $\kappa_{1}(G)$ of a regular graph $G$ under some conditions are shown. Furthermore, the following new results are gotten: the pessimistic diagnosability $t_p(S_n^2)=4n-9$ for split-star networks $S_n^2$, $t_p(\Gamma_n)=2n-4$ for Cayley graphs generated by transposition trees $\Gamma_n$, $t_p(\Gamma_{n}(\Delta))=4n-11$ for Cayley graph generated by the $2$-tree $\Gamma_{n}(\Delta)$, $t_{p}(BP_n)=2n-2$ for the burnt pancake networks $BP_n$. As corollaries, the known results about the extra connectivity and the pessimistic diagnosability of many famous networks including the alternating group graphs, the alternating group networks, BC networks, the $k$-ary $n$-cube networks etc. are obtained directly. Comment: 23 pages |
| نوع الوثيقة: | Working Paper |
| URL الوصول: | http://arxiv.org/abs/1701.08355 |
| رقم الأكسشن: | edsarx.1701.08355 |
| قاعدة البيانات: | arXiv |
| الوصف غير متاح. |