Reliability Analysis of ( n, k )-Bubble-Sort Networks Based on Extra Conditional Fault

Lina Zhao, Shiying Wang () and Feng Dou
Additional contact information
Lina Zhao: School of Mathematics and Computer Science, Shanxi Normal University, Taiyuan 030031, China
Shiying Wang: School of Mathematics and Computer Science, Shanxi Normal University, Taiyuan 030031, China
Feng Dou: School of Mathematics and Computer Science, Shanxi Normal University, Taiyuan 030031, China

Mathematics, 2024, vol. 12, issue 18, 1-11

Abstract: Given a graph G = ( V ( G ) , V ( E ) ) , a non-negative integer g and a set of faulty vertices F ⊆ V ( G ) , the g -extra connectivity of G , denoted by κ g ( G ) , is the smallest cardinality of F , whose value of deletion, if exists, will disconnect G and give each remaining component at least g + 1 vertices. The g -extra diagnosability of the graph G , denoted by t g ( G ) , is the maximum cardinality of the set F of fault vertices that the graph can guarantee to identify under the condition that each fault-free component has more than g vertices. In this paper, we determine that g -extra connectivity of ( n , k ) -bubble-sort network B n , k is κ g ( B n , k ) = n + g ( k − 2 ) − 1 for 4 ≤ k ≤ n − 1 and 0 ≤ g ≤ n − k . Afterwards, we show that g -extra diagnosability of B n , k under the PMC model ( 4 ≤ k ≤ n − 1 and 0 ≤ g ≤ n − k ) and MM* model ( 4 ≤ k ≤ n − 1 and 0 ≤ g ≤ min { n − k − 1 , k − 2 } ) is t g ( B n , k ) = n + g ( k − 1 ) − 1 , respectively.

Keywords: ( n , k )-bubble-sort network; g -extra connectivity; g -extra diagnosability; PMC model; MM* model (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2024
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/12/18/2939/pdf (application/pdf)
https://www.mdpi.com/2227-7390/12/18/2939/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:12:y:2024:i:18:p:2939-:d:1482621

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().