TCS Journal 2026 Journal Article
Extra path-structure connectivity of modified bubble-sort networks
- Guozhen Zhang
- Tao Wen
- Dajin Wang
A network’s connectivity is a crucial indicator for its reliability. There are various ways to measure the connectivity, and the extra connectivity and the structure connectivity are two variants of the classic, original connectivity. In this paper, we incorporate the two to study the extra structure connectivity for the modified bubble-sort network MBn, which is one of the proposed models for the interconnection network of multiprocessor systems. Let H be a connected subgraph of a graph G, and let F = { H 1, H 2, …, H j } be a set of subgraphs of G, such that 1) each Hi is isomorphic to H; 2) G − F is disconnected; and 3) each component of G − F has at least g + 1 nodes. The minimum j for such an F is called the g-extra H-structure connectivity of G, denoted κg (G; H). Let F = { J 1, J 2, …, J k } be a set of subgraphs of G, such that 1) each Ji is isomorphic to a subgraph of H; 2) G − F is disconnected; and 3) each component of G − F has at least g + 1 nodes. The minimum k for such an F is called the g-extra H-substructure connectivity of G, denoted κ g s ( G; H ). We will prove that for P 3l, a path on 3l nodes, κ 1 ( M B n; P 3 l ) = κ 1 s ( M B n; P 3 l ) = ⌈ n − 1 l ⌉ for n ≥ 9 and l ≤ n − 2.