On the \(\ell\)-connectivity of a graph
type: Item
instance of: scholarly article
title: On the \(\ell\)-connectivity of a graph
zbMATH Open document ID: 0631.05031
DOI: 10.1007/BF01788551
author: Ortrud R. Oellermann
published in: Graphs and Combinatorics
publication date: 1987-01-01T00:00:00Z
review text: Let be \(\ell \geq 2\), then the \(\ell\)-connectivity of a graph G, \(\kappa_{\ell}(G)\), in the minimum number of vertices whose removal produces a disconnected graph with at least \(\ell\) components or a graph with fewer than \(\ell\) vertices. A graph is said to be (n,\(\ell)\)- connected if \(\kappa_{\ell}(G)\geq n\). \textit{G. Chartrand, S. F. Kapoor, L. Lesniak} and \textit{D. R. Lick} [Bull. Bombay Math. Colloq. 2, 1-6 (1984)] proved that a graph of order p with independence number \(\beta\) (G)\(\geq \ell \geq 2\) is (n,\(\ell)\)-connected if the minimal degree \(\delta (G)\geq [p+(\ell -1)(n-2)]/\ell\). Improving a result of \textit{J. Bondy} [Studia Sci. Math. Hung. 4, 473-475 (1969; Zbl 0184.277)] the author states that a graph G of order \(p\geq 2\) is (n,\(\ell)\)-connected if the degree-sequence \(d_ 1\leq...\leq d_ p\) fulfills \((d_ k\leq k+n- 2)\Rightarrow (d_{p-n+1}\geq p-k(\ell -1))\) for each k with \(1\leq k\leq \lfloor (p-n+1)/\ell \rfloor\). Also she gives a sufficient condition for a graph to contain at least n internally disjoint S-paths (S a set of \(\ell\) vertices of G) in terms of the minimal degree using the theorem of Chartrand et al.
Mathematics Subject Classification ID: 05C40
zbMATH DE Number: 4025474
reviewed by: Michael Hager
MaRDI profile type: Publication
cites work: Q5576241
cites work: A sufficient condition for n ‐connectedness of graphs
cites work: Q3335824
cites work: Q3818315
cites work: A Sufficient Condition for n-Short-Connectedness
cites work: Über die Maximalzahl kreuzungsfreier H-Wege
Recommended article: Q3113189
Recommended article: A generalization of an edge-connectivity theorem of Chartrand
Recommended article: High connectivity keeping sets in \(n\)-connected graphs
Recommended article: Q4847796
Recommended article: On Vertices of Degree n in Minimally n-Edge-Connected Graphs
Recommended article: Q4878669
Recommended article: Making the components of a graph \(k\)-connected
Recommended article: Minimum degree, independence number and regular factors
Recommended article: An improved lower bound on the independence number of a graph
Recommended article: Bounds on the size of graphs of given order and \(l\)-connectivity
description: scientific article; zbMATH DE number 4025474