Fault-Tolerant Maximal Local-Connectivity on Leaf-Sort Graphs

An interconnection network is usually modeled as a graph, in which vertices and edges correspond to processors and communication links, respectively. Connectivity is an important index to measure the fault-tolerant capability of interconnection networks. A graph [Formula: see text] is called to be maximally local-connected if each pair of vertices [Formula: see text] and [Formula: see text] of [Formula: see text] are connected by min[Formula: see text] vertex-disjoint paths. A graph [Formula: see text] is [Formula: see text]-fault-tolerant maximally local-connected if [Formula: see text] remains maximally local-connected for any [Formula: see text] with [Formula: see text]. In this paper, we show that the [Formula: see text]-dimensional leaf-sort graph [Formula: see text] is [Formula: see text]-fault-tolerant maximally local-connected for [Formula: see text]; under the restricted condition that each vertex has at least two fault-free adjacent vertices, [Formula: see text] is [Formula: see text]-conditional fault-tolerant maximally local-connected for odd [Formula: see text] and [Formula: see text]-conditional fault-tolerant maximally local-connected for even [Formula: see text]. Furthermore, we show that [Formula: see text] is [Formula: see text]-fault-tolerant one-to-many maximally local-connected for [Formula: see text].