The Sufficient Conditions of (δ(G) - 2)-(|F|-)Fault-Tolerant Maximal Local-(Edge-)Connectivity of Connected Graphs

An interconnection network is usually modeled by a connected graph in which vertices represent processors and edges represent links between processors. The connectivity is an important parameter to evaluate the fault tolerance of interconnection networks. A connected graph G is maximally local-(edge-)connected if each pair vertices x, y of G is connected by min{d(G)(x), d(G)(y) } pairwise (edge-)disjoint paths between x and y in G. A graph G is called m-fault-tolerant maximally local-(edge-)connected if G- F is maximally local-(edge-)connected for any F subset of V(G) (E(G)) with vertical bar F vertical bar <= m. A graph G is called m-fault-tolerant maximally local-(edge-)connected of order r if G - F is maximally local-(edge-)connected for any F subset of V(G) (E(G)) with vertical bar F vertical bar <= m, where F is a conditional faulty vertex (edge) set of order r. In this paper, we obtain the sufficient condition of connected graphs to be (delta(G) - 2)-edge-fault-tolerant maximally local-edge-connected. Moreover, we consider the sufficient condition of connected graphs to be vertical bar F vertical bar-fault-tolerant maximally local-(edge-)connected of order r. Some previous results in [Theor. Comput. Sci. 731 (2018) 50-67] and [Theor. Comput. Sci. 847 (2020) 39-48] are extended.

Automated summary

This paper investigates the connectivity and fault tolerance of connected graphs, providing definitions for maximally local-connected and maximally local-edge-connected graphs. By studying their sufficient conditions, the previous research findings are extended.