Reliability evaluation of Modified bubble-sort graph networks based on structure fault pattern

Na Wang, Jixiang Meng and Yingzhi Tian

Applied Mathematics and Computation, 2022, vol. 430, issue C

Abstract: Let G be a graph and H be a fixed connected subgraph. Let H={H1,H2,⋯,Hk} be a set of connected subgraphs of G. The H-structure connectivity (resp. H-substructure connectivity) κ(G;H) (resp. κs(G;H)) is defined as the least cardinality of H such that Hi is isomorphic to H (resp. a connected subgraph of H) for any 1≤i≤k, and H’s deletion makes G disconnected or trivial. As an extension of the classic connectivity, the H-structure (resp. H-substructure) connectivity can better evaluate the fault-tolerance of an interconnection network. In this paper, we focus on the n-dimensional modified bubble-sort graph MBn. We determine κ(MBn;Pl) (resp. κs(MBn;Pl), where n≥5, 2≤l≤2n, and Pl is a path on l vertices; κ(MBn;C2l) (resp. κs(MBn;C2l)), where 6≤2l≤n, and C2l is a cycle on 2l vertices; κ(MBn;T2l) (resp. κs(MBn;T2l)), where 1≤l≤n−2 and T2l is an l-leaves 2-step star. In addition, we give the upper bound of κ(MBn;K1,l) (resp. κs(MBn;K1,l)), where n≥4 and 2≤l≤n and K1,l is a star on l+1 vertices, and prove that the upper bounds are sharp for l=2,3,4.

Keywords: Modified bubble-sort graph; Fault-tolerance; Structure connectivity; Substructure connectivity (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0096300322003319
Full text for ScienceDirect subscribers only

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:eee:apmaco:v:430:y:2022:i:c:s0096300322003319

DOI: 10.1016/j.amc.2022.127257

Access Statistics for this article

Applied Mathematics and Computation is currently edited by Theodore Simos

More articles in Applied Mathematics and Computation from Elsevier
Bibliographic data for series maintained by Catherine Liu ().