×

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

MSC:

05C40 Connectivity

Citations:

Zbl 0184.277
PDFBibTeX XMLCite
Full Text: DOI

References:

[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
[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
[6] Mader, W.: Über die Maximahlzahl kreuzungsfreierH-Wege. Arch. Math.31, 387–402 (1978/79) · Zbl 0378.05038
[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
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.