The connected cutset connectivity of a graph (Q1101465)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | The connected cutset connectivity of a graph |
scientific article |
Statements
The connected cutset connectivity of a graph (English)
0 references
1988
0 references
The connected (edge-)cutset connectivity \(c\kappa\) (G) \((c\kappa_ 1(G))\) of a graph G is the minimum cardinality of a vertex (edge) cutset S of G such that the subgraph induced by S is connected. Let \(\kappa\) (G) be the vertex-connectivity of G, \(\kappa_ 1(G)\) the edge-connectivity and \(\delta\) (G) the minimal degree. The author proves existence theorems for graphs with given \(\kappa\) (G), \(c\kappa\) (G), \(\delta\) (G) as well as given \(\kappa_ 1(G)\), \(c\kappa_ 1(G)\), \(\delta\) (G) and shows that for graphs with \(c\kappa_ 1(G)\subseteq c\kappa (G)\) holds \(c\kappa_ 1(G)=\delta (G)\).
0 references
minimum degree
0 references
edge-connectivity
0 references