Graphs with the smallest number of minimum cut sets

The number of vertex cut sets of size k in a graph of connectivity k has been used as a measure of network reliability. Let G be a regular graph with N vertices, valency k , connectivity k , and with the minimum number of vertex cut sets with k vertices. The problem of constructing such a graph G for each pair ( N, k ) is known to be difficult. We show how to construct infinite families of such graphs in various cases. These cases are spread through the range 3/8 ≤ k/N <1. We also deal with cases in which k is small and cases with N ‐ k small.