Two kinds of generalized connectivity of dual cubes

Let S subset of V(G) and kappa(G)(S) denote the maximum number k of edge-disjoint trees T-1, T-2 , . . . , T-k in G such that V(T-i) boolean AND V(T-j) = S for any i, j is an element of (1, 2, . . . , k} and i not equal j. For an integer r with 2 <= r <= n, the generalized r-connectivity of a graph G is defined as kappa(r)(G) = min{kappa(G)(S)vertical bar S subset of V(G) and vertical bar S vertical bar = r}. The r-component connectivity c kappa(r)(G) of a non-complete graph G is the minimum number of vertices whose deletion results in a graph with at least r components. These two parameters are both generalizations of traditional connectivity. Except hypercubes and complete bipartite graphs, almost all known kappa(r)(G) are about r = 3. In this paper, we focus on kappa(4)(D-n) of dual cube D-n. We first show that kappa(4)(D-n) = n - 1 for n >= 4. As a corollary, we obtain that kappa(3)(D-n) = n - 1 for n >= 4. Furthermore, we show that C kappa(r+1)(D-n) = rn - r(r + 1)/2 + 1 for n >= 2 and 1 <= r <= n -1. (C) 2018 Elsevier B.V. All rights reserved.