Fault-Tolerant Strong Menger (Edge) Connectivity of DCC Linear Congruential Graphs

With the rapid development and advances of very large scale integration technology and wafer-scale integration technology, multiprocessor systems, taking interconnection networks as underlying topologies, have been widely designed and used in big data era. The topology of an interconnection network is usually represented as a graph. If any two distinct vertices x, y in a connected graph G are connected by min{deg(G)(x), deg(G)(y)} vertex (edge)-disjoint paths, then G is called strongly Menger (edge) connected. In 1996, Opatrny et al. [16] introduced the DCC (Disjoint Consecutive Cycle) linear congruential graph, which consists of n nodes and is generated by a set of linear functions F with special properties. In this work, we investigate the strong Menger connectivity of the DCC linear congruential graph G = G(2t) (F, 2(p)) with faulty vertices or edges, where 2 <= t <= p - 1,p >= 5, F = {f(i)(x)vertical bar f(i)(x) = (2(i - 1)b+1)x + 2(i-1)c, 1 <= i <= t}, gcd(c, 2(p)) = 1 and b is a multiple of 4. In detail, we show that G - S is strongly Menger connected if vertical bar S vertical bar <= 2t - 4 for any S subset of V(G). Moreover, we determine that G - S is strongly Menger edge connected if vertical bar S vertical bar <= 2t - 2 for any S subset of E(G). Furthermore, we prove that, under the restricted condition delta(G - S) >= 2, G - S is strongly Menger edge connected if vertical bar S vertical bar <= 4t - 6 and t >= 3 for any S subset of E(G). In addition, we present some empirical examples to show that the bounds are all optimal in the sense of the maximum number of tolerable edge faults.

Automated summary

This paper investigates the strong Menger connectivity of the DCC linear congruential graph with faulty vertices or edges. Based on empirical examples and mathematical proofs, the boundaries of strong Menger connectivity under different conditions are determined.