Premium
Graphs with the smallest number of minimum cut sets
Author(s) -
Smith Derek
Publication year - 1984
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.3230140105
Subject(s) - combinatorics , valency , mathematics , vertex (graph theory) , discrete mathematics , graph , neighbourhood (mathematics) , mathematical analysis , philosophy , linguistics
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.