chapter  7
30 Pages

Partitions of the VertexSet and Vertex Separators

A subset F of the edge set E of a graph G = (V;E) de…nes in a natural way a partition of the vertex set V . The blocks (subsets) of the partition are formed by vertices that belong to the same component of (V; F ). Partitions can be employed in order to de…ne more general reliability measures. We will pursue this idea in the last section of this chapter.