zbMATH — the first resource for mathematics

On the \(\ell\)-connectivity of a graph. (English) Zbl 0631.05031
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\). G. Chartrand, S. F. Kapoor, L. Lesniak and 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 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.
Reviewer: M.Hager

05C40 Connectivity
Full Text: DOI
[1] Bondy, J.A.: Properties of graphs with constraints on degrees. Stud. Sci. Math. Hung.4, 473–475 (1969) · Zbl 0184.27702
[2] Chartrand, G., Kapoor, S.F., Kronk, H.V.: A sufficient condition forn-connectedness of graphs. Mathematika15, 51–52 (1968) · Zbl 0175.20703 · doi:10.1112/S0025579300002369
[3] Chartrand, G., Kapoor, S.F., Lesniak, L., Lick, D.R.: Generalized connectivity in graphs. Bull. Bombay Math. Colloq.2, 1–6 (1984) · Zbl 0545.05052
[4] Chartrand, G., Lesniak, L.: Graphs & Digraphs, Second Edition. Monterey: Wadsworth & Brooks/Cole 1986 · Zbl 0666.05001
[5] Hedman, B.: A sufficient condition forn-short-connectedness. Math. Mag.47, 156–157 (1974) · Zbl 0295.05111 · doi:10.2307/2689276
[6] Mader, W.: Über die Maximahlzahl kreuzungsfreierH-Wege. Arch. Math.31, 387–402 (1978/79) · Zbl 0378.05038 · doi:10.1007/BF01226465
[7] Menger, K.: Zur allgemeinen Kurventheorie. Fund. Math.10, 96–115 (1927) · JFM 53.0561.01
[8] Whitney, H.: Congruent graphs and the connectivity of graphs. Amer. J. Math.54, 150–168 (1932) · JFM 58.0609.01 · doi:10.2307/2371086
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.