×

The connected cutset connectivity of a graph. (English) Zbl 0643.05044

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)\).
Reviewer: M.Hager

MSC:

05C40 Connectivity
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Chartrand, G., A graph theoretic approach to a communications problem, SIAM J. Appl. Math., 14, 778-781 (1966) · Zbl 0145.20605
[2] Chartrand, G.; Kaugars, A.; Lick, D. R., Critically \(n\)-connected graphs, Proc. Amer. Math. Soc., 32, 63-68 (1972) · Zbl 0211.27002
[3] Chartrand, G.; Lesniak, L., Graphs and Digraphs (1986), Wadsworth & Brooks/Cole: Wadsworth & Brooks/Cole Monterey · Zbl 0666.05001
[4] A.H. Esfahanian, On restricted connectivities, in preparation.; A.H. Esfahanian, On restricted connectivities, in preparation.
[5] Goldsmith, D. L.; Entringer, R. C., A sufficient condition for equality of edge-connectivity and the minimum degree of a graph, J. Graph Theory, 3, 251-255 (1979) · Zbl 0417.05040
[6] Goldsmith, D. L.; White, A. T., On graphs with equal edge-connectivity and minimum degree, Discrete Math., 23, 31-36 (1978) · Zbl 0393.05035
[7] Lesniak, L., Results on the edge-connectivity of graphs, Discrete Math., 8, 351-354 (1974) · Zbl 0277.05123
[8] Plesnik, J., Critical graphs of given diameter, Acta Fac. Rerum. Natur. Univ. Comenian Math., 30, 71-93 (1975) · Zbl 0318.05115
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.