Graphs with the smallest number of minimum cut sets
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.... We show how to construct infinite families of such graphs in... cases... spread through the range \(3/8\leq k/N<1\). We also deal with cases in which k is small and cases with N-k small. For example, a regular graph G is of type X if G consists of a subgraph G' together with a number r(r\(\geq 1)\) of vertices which are adjacent to every vertex of G'.... Theorem 1: Let G be a regular graph of connectivity k, valency k, with N vertices and q vertex cut-sets with k vertices. Then either G is of type X, or \(q(N- k)\geq 3N\). Theorem 2: If G has valency 3 and connectivity 3, then either G is \(K_{3,3}\) or G has at least N vertex cut-sets with three vertices. Construction B: Let \(G_ 1\) be a graph with \(N=2p\), and vertices \(v_ 0,v_ 1,...,v_{2p-1}\). Vertices \(v_ i\) and \(v_ j\) are joined if \(i-j\equiv \pm 1(mod N)\) or if \(j\equiv i+p(mod N).\)... Theorem 3: The graph of valency 3 with the minimum number of vertex cut-sets with three vertices is \(K_{3,3}(N=6)\), and the graph constructed in Construction B (N\(\geq 8).\) Theorem 4: Let G be a regular graph with valency 4, connectivity 4, and \(N\geq 14\) vertices. Then, if q denotes the number of vertex cut-sets with 4 vertices, \(q\geq 3/4N.\) Theorem 6: If \(N=kv,\quad m=(k-1)v,\) then for each \(i=0,1,...,v-2\), the complete multipartite graph \(K_{v,v,...,v}\) with kv vertices has the smallest number of distinct vertex cut sets of size \((k-1)v+i\) of all m- connected, m-valent graphs with N vertices.
- Optimally reliable networks
- Super edge-connectivity of dense digraphs and graphs
- Number of minimum vertex cuts in transitive graphs
- On the number of small cut in a graph
- Graphs with largest number of minimum cuts
- Solution methods for the vertex variant of the network system vulnerability analysis problem
- Minimal 2-connected graphs satisfying the even cut condition
- Cutsets in perfect and minimal imperfect graphs
- Minimum weight resolving sets of grid graphs
- Minimum cut with the fewest number of arcs
- scientific article; zbMATH DE number 5131681 (Why is no real title available?)
- Counting the number of minimum cuts in undirected multigraphs
- Optimally Reliable Graphs for Both Vertex and Edge Failures
- An exact lower bound on the number of cut‐sets in multigraphs
- From connectivity to coloring
- On the Number of Minimum Cuts in a Graph
- scientific article; zbMATH DE number 1404133 (Why is no real title available?)
- Smallest Graphs Achieving the Stinson Bound
- scientific article; zbMATH DE number 6783459 (Why is no real title available?)
- Minimal graph cuts on network subgraphs
- Minimum Cuts in Surface Graphs
- Superconnectivity for minimal multi-loop networks
This page was built for publication: Graphs with the smallest number of minimum cut sets
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3344017)