Some Results on Generalized Connectivity With Applications to Topological Design of Fault-Tolerant Multicomputers

Abstract

The connectivity of a graph \(G(V, E)\) is the least cardinality \(|S|\) of a vertex set \(S\) such that \(G – S\) is either disconnected or trivial. This notion of connectivity has been generalized in two ways: one by imposing some graphical property on the set \(S\), and the other by imposing some graphical property on the components of the graph \(G – S\). In this paper, we study some instances of each of the above generalizations.

First, we prove that the problem of finding the least cardinality \(|S|\) such that the graph \(G – S\) is disconnected and one of the following properties (i) – (iii) is satisfied, is NP-hard: (i) given a set of forbidden pairs of vertices, the set \(S\) does not contain a forbidden pair of vertices; (ii) the set \(S\) does not contain the neighborhood of any vertex in \(G\); (iii) no component of \(G – S\) is trivial.
We then show that the problem satisfying property (ii) or (iii) has a polynomial-time solution if \(G\) is a \(k\)-tree. Applications of the above generalizations and the implications of our results to the topological design of fault-tolerant networks are discussed.