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.