On the \(\ell\)-connectivity of a graph (Q1094432): Difference between revisions

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.