Fault-tolerant strong Menger connectivity of modified bubble-sort graphs*,**

An interconnection network is usually modeled as a graph, in which vertices and edges correspond to processors and communication links, respectively. For the study of graphs, connectivity and edge connectivity are the basic issues, and the discussion of fault tolerance is based on connectivity. A connected graph G is strongly Menger connected if each pair of vertices u and v of G, there are min{dG(u), dG(v)} vertex-disjoint paths connecting u and v. G is m-fault-tolerant strongly Menger connected if G - F remains strongly Menger connected for any F C V (G) with |F| < m. G is m-conditional faulttolerant strongly Menger connected if G - F remains strongly Menger connected for any F C V (G) with | F | < m and & delta;(G - F) > 2. In this paper, we demonstrate that n-dimensional modified bubble-sort graphs MBn is (n - 2)-fault-tolerant strongly Menger connected and (n - 2)-fault-tolerant one-to-many strongly Menger connected for n > 4. Moreover, under the restricted condition that each vertex has at least two fault-free adjacent vertices, MBn is (2n - 5)-conditional fault-tolerant strongly Menger connected for n > 4. & COPY; 2023 Elsevier B.V. All rights reserved.

Automated summary

An interconnection network is modeled as a graph, with vertices representing processors and edges representing communication links. Connectivity and edge connectivity are fundamental issues in graph theory, and fault tolerance is based on connectivity. This paper demonstrates the fault tolerance and connectivity properties of the n-dimensional modified bubble-sort graph MBn.