Two kinds of generalized connectivity of dual cubes

Abstract

Let $S\subseteq V(G)$ and ${\kappa }_G(S)$ denote the maximum number $k$ of edge-disjoint trees $T_1,T_2,\cdots ,T_k$ in $G$ such that $V(T_i)\bigcap V(T_j)=S$ for any $i,j\in \{1,2,\cdots ,k\}$ and $i\ne j$. For an integer $r$ with $2\le r\le n$, the {\em generalized $r$-connectivity} of a graph $G$ is defined as ${\kappa }_r(G)=min\{{\kappa }_G(S)|S\subseteq V(G)$ and $|S|=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\ge 4$. As a corollary, we obtain ${\kappa }_3(D_n)=n-1$ for $n\ge 4$. Furthermore, we show that $c{\kappa }_{r+1}(D_n)=rn-\frac{r(r+1)}{2}+1$ for $n\ge 2$ and $1\le r\le n-1$.