The connectivity is an important measurement for the fault tolerance of a network. Let G = (V(G), E(G)) be a connected graph with the vertex set V(G) and edge set E(G). An S‐tree of graph G is a tree T that contains all the vertices in S subject to S⊆V(G). Two S‐trees T and T^′ are internally disjoint if and only if E(T)∩E(T^′) = ∅ and V(T)∩V(T^′) = S. Denote κ_G(S) by the maximum number of internally disjoint S‐trees in graph G. The generalized k‐connectivity is a natural generalization of the classical connectivity, which is defined as κ_r(G) = min{κ_G(S)|S⊆V(G)and|S| = r}. In this paper, we mainly focus on the generalized connectivity of cube‐connected‐cycle CCC_n and hierarchical hypercube HHC_n, which were introduced for massively parallel systems. We show that for n = 2^m + 2(m ≥ 1), κ₄(HHC_n) = m and κ₄(CCC_n) = 2, that is, for any four vertices in CCC_n (or HHC_n), there exist 2 (or m) internally disjoint S‐trees connecting them in CCC_n (or HHC_n).

The g-extra connectivity is a very important index to evaluate the fault tolerance, reliability of interconnection networks. Let g be a non-negative integer, G be a connected graph with vertex set V and edge set E, a subset $S\subseteq V$ is called a g-extra cut of G if the graph induced by the set $G-S$ is disconnected and each component of $G-S$ has at least $g+1$ vertices. The g-extra connectivity of G, denoted as ${\kappa }_g\left(G\right)$, is the cardinality of the minimum g-extra cut of G. Mycielski introduced a graph transformation to discover chromatic numbers of triangle-free graphs that can be arbitrarily large. This transformation converts a graph G into a new compound graph called $\mu \left(G\right)$, also known as the Mycielskian graph of G. In this paper, we study the relationship on g-extra connectivity between the Mycielskian graph $\mu \left(G\right)$ and the graph G. In addition, we show that ${\kappa }_3\left(\mu \left(G\right)\right)=2{\kappa }_1\left(G\right)+1$ for ${\kappa }_1\left(G\right)\le min\{4,\lfloor \frac{n}{2}\rfloor \}$, and prove the bounds of ${\kappa }_{2g+1}\left(\mu \left(G\right)\right)$ for $g\ge 2$.

The $k$-set tree connectivity, as a natural extension of classical connectivity, is a very important index to evaluate the fault-tolerance of interconnection networks. Let $G=(V, E)$ be a connected graph and a subset $S\subseteq V$, an $S$-tree of graph $G$ is a tree $T=(V',E')$ that contains all the vertices of $S$. Two $S$-trees $T$ and $T'$ are internally disjoint if and only if $E(T)\cap E(T')=\varnothing$ and $V(T)\cap V(T')=S$. The cardinality of maximum internally disjoint $S$-trees is defined as $\kappa_{G}(S)$, and the $k$-set tree connectivity is defined by $\kappa_{k}(G)=\min\{\kappa_{G}(S)|S\subseteq V(G)\ \text{and} \ |S|=k\}$. In this paper, we show that the $k$-set tree connectivity of hierarchical folded hypercube when $k=4$, that is, $\kappa_{4}(HFQ_{n})=n+1$, where $HFQ_{n}$ is hierarchical folded hypercube for $n\geq 7$.