Graphs with the smallest number of minimum cut sets

From MaRDI portal
Publication:3344017





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.











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)