On the optimal vertex-connectivity augmentation
type: Item
instance of: scholarly article
title: On the optimal vertex-connectivity augmentation
zbMATH Open document ID: 0824.05042
author: Tibor Jordán
published in: Journal of Combinatorial Theory. Series B
publication date: 1995-07-02T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 05C40
Mathematics Subject Classification ID: 05C35
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 767677
zbMATH Keywords: vertex-connectivity
zbMATH Keywords: polynomial-time algorithm
zbMATH Keywords: optimal vertex- connectivity augmentation
zbMATH Keywords: \(k\)-connected graph
zbMATH Keywords: tight sets
reviewed by: Radim Jiroušek
MaRDI profile type: Publication
full work available at URL: jctb.1995.1002
OpenAlex ID: W2048815229
DOI: 10.1006/JCTB.1995.1002
description: scientific article; zbMATH DE number 767677