On the l-connectivity of a diagraph

AbstractThe strong independence number βs(D) of a digraph D is the maximum cardinality of a set S of vertices of D so that the subdigraph induced by S is acyclic. For an integer l ⩾ 2, and a digraph D, the strong l-connectivity κl(D) (strong l-arc connectivity λl(D)) of D is the minimum number of vertices (arcs) whose deletion from D produces a digraph with at least l strong components or a digraph with at most l − 1 vertices. For an integer n ⩾ 0, a digraph D is said to be strongly (n, l)-connected if κl(D) ⩾ n. Several sufficient conditions for a digraph to be strongly (n, l)-connected are established. Let D be a digraph on p vertices. Then the sequence of numbers κ2(D), κ3(D), …, κp(D) is called the sequence of strong connectivity numbers of D. Sequences of nonnegative integers that are sequences of strong connectivity numbers of digraphs are characterized. For a given integer l ⩾ 2 the strong l-connectivity function fl of a digraph D on p ⩾ l − 1 vertices and with κl(D) = κl is is defined as follows: fl: {0, 1, …, κl}→N⌣ {0} and for 0 < k < κl, fl(k) = sk where sk is the minimum strong l-arc-connectivity among all subdigraphs of D obtained by deleting k vertices from D. The strong 2-connectivity functions of digraphs (and in particular also of asymmetric digraphs) are characterized. Further, several necessary conditions for a function to be the strong l-connectivity function of a digraph are established