Extra path-structure connectivity of modified bubble-sort networks

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 MB_n, 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₁,H₂,…,H_j} be a set of subgraphs of G, such that 1) each H_i 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₁,J₂,…,J_k} be a set of subgraphs of G, such that 1) each J_i 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, [Formula presented] for n ≥ 9 and l≤n−2.