Immunity to Subgraph Failures in Communication Networks
Arthur M. Farley, Andrzej Proskurowski
Committee:
Technical Report(May 1987)
Keywords:

A network is immune to a set of failures F if message transfer can be completed in the presence of F. In this paper, we describe networks immune to certain classes of templated failures. A templated failure is characterized by (possibly more than one) connected graph, a template; elements of a given network that belong to a subgraph isomorphic with a template can fail together as a dependent failure. We discuss templates that can be described as graphs induced by a single node and a subset of its neighbors. We first deal with immu­nity to single templated failures. We then consider networks immune to sets of isolated failures, wherein no two adjacent elements of the network may fail. We describe minimal classes of graphs immune to sets of isolated failures characterized by a K1,1 template