On the optimal vertex-connectivity augmentation (Q1892828): Difference between revisions

The optimal vertex-connectivity augmentation problem denotes the task of finding the minimum set of edges that should be added to a graph to increase its vertex-connectivity. The cardinality of such a minimal set for a graph \(G\) is denoted \(m(G)\). The author considers simple graphs and proves that for any \(k\)-connected graph \(G\) \((k\geq 2)\), \[ \max\{b(G)- 1, \lceil t(G)/2\rceil\}\leq m(G)\leq \max\{b(G)- 1, \lceil t(G)/2\rceil\} k- 2, \] where \(b(G)\) denotes the maximum number of components that can be achieved by removing \(k\) vertices from the graph \(G\), and \(t(G)\) equals the maximum number of pairwise disjoint minimal tight sets.