Abstract A connected graph $G$ is called strongly Menger (edge) connected if for any two distinct vertices $x,y$ of $G$, there are $\min \{\textrm{deg}_G(x), \textrm{deg}_G(y)\}$ internally disjoint (edge disjoint) paths between $x$ and $y$. Motivated by parallel routing in networks with faults, Oh and Chen (resp., Qiao and Yang) proposed the (fault-tolerant) strong Menger (edge) connectivity as follows. A graph $G$ is called $m$-strongly Menger (edge) connected if $G-F$ remains strongly Menger (edge) connected for an arbitrary vertex set $F\subseteq V(G)$ (resp. edge set $F\subseteq E(G)$) with $|F|\leq m$. A graph $G$ is called $m$-conditional strongly Menger (edge) connected if $G-F$ remains strongly Menger (edge) connected for an arbitrary vertex set $F\subseteq V(G)$ (resp. edge set $F\subseteq E(G)$) with $|F|\leq m$ and $\delta (G-F)\geq 2$. In this paper, we consider strong Menger (edge) connectedness of the augmented $k$-ary $n$-cube $AQ_{n,k}$, which is a variant of $k$-ary $n$-cube $Q_n^k$. By exploring the topological proprieties of $AQ_{n,k}$, we show that $AQ_{n,3}$ (resp. $AQ_{n,k}$, $k\geq 4$) is $(4n-9)$-strongly (resp. $(4n-8)$-strongly) Menger connected for $n\geq 4$ (resp. $n\geq 2$) and $AQ_{n,k}$ is $(4n-4)$-strongly Menger edge connected for $n\geq 2$ and $k\geq 3$. Moreover, we obtain that $AQ_{n,k}$ is $(8n-10)$-conditional strongly Menger edge connected for $n\geq 2$ and $k\geq 3$. These results are all optimal in the sense of the maximum number of tolerated vertex (resp. edge) faults.

Abstract Given a connected graph $G$ and a positive integer $\ell $, the $\ell $-extra (resp. $\ell $-component) edge connectivity of $G$, denoted by $\lambda ^{(\ell )}(G)$ (resp. $\lambda _{\ell }(G)$), is the minimum number of edges whose removal from $G$ results in a disconnected graph so that every component has more than $\ell $ vertices (resp. so that it contains at least $\ell $ components). This naturally generalizes the classical edge connectivity of graphs defined in term of the minimum edge cut. In this paper, we proposed a general approach to derive component (resp. extra) edge connectivity for a connected graph $G$. For a connected graph $G$, let $S$ be a vertex subset of $G$ for $G\in \{\Gamma _{n}(\Delta ),AG_n,S_n^2\}$ such that $|S|=s\leq |V(G)|/2$, $G[S]$ is connected and $|E(S,G-S)|=\min \limits _{U\subseteq V(G)}\{|E(U, G-U)|: |U|=s, G[U]\ \textrm{is connected}\ \}$, then we prove that $\lambda ^{(s-1)}(G)=|E(S,G-S)|$ and $\lambda _{s+1}(G)=|E(S,G-S)|+|E(G[S])|$ for $s=3,4,5$. By exploring the reliability analysis of $AG_n$ and $S_n^2$ based on extra (component) edge faults, we obtain the following results: (i) $\lambda _3(AG_n)-1=\lambda ^{(1)}(AG_n)=4n-10$, $\lambda _4(AG_n)-3=\lambda ^{(2)}(AG_n)=6n-18$ and $\lambda _5(AG_n)-4=\lambda ^{(3)}(AG_n)=8n-24$; (ii) $\lambda _3(S_n^2)-1=\lambda ^{(1)}(S_n^2)=4n-8$, $\lambda _4(S_n^2)-3=\lambda ^{(2)}(S_n^2)=6n-15$ and $\lambda _5(S_n^2)-4=\lambda ^{(3)}(S_n^2)=8n-20$. This general approach maybe applied to many diverse networks.

Abstract For an integer $\ell \geqslant 2$, the $\ell $-component connectivity (resp. $\ell $-component edge connectivity) of a graph $G$, denoted by $\kappa _{\ell }(G)$ (resp. $\lambda _{\ell }(G)$), is the minimum number of vertices (resp. edges) whose removal from $G$ results in a disconnected graph with at least $\ell $ components. The two parameters naturally generalize the classical connectivity and edge connectivity of graphs defined in term of the minimum vertex-cut and the minimum edge-cut, respectively. The two kinds of connectivities can help us to measure the robustness of the graph corresponding to a network. In this paper, by exploring algebraic and combinatorial properties of $n$-dimensional balanced hypercubes $BH_n$, we obtain the $\ell $-component (edge) connectivity $\kappa _{\ell }(BH_n)$ ($\lambda _{\ell }(BH_n)$). For $\ell $-component connectivity, we prove that $\kappa _2(BH_n)=\kappa _3(BH_n)=2n$ for $n\geq 2$, $\kappa _4(BH_n)=\kappa _5(BH_n)=4n-2$ for $n\geq 4$, $\kappa _6(BH_n)=\kappa _7(BH_n)=6n-6$ for $n\geq 5$. For $\ell $-component edge connectivity, we prove that $\lambda _3(BH_n)=4n-1$, $\lambda _4(BH_n)=6n-2$ for $n\geq 2$ and $\lambda _5(BH_n)=8n-4$ for $n\geq 3$. Moreover, we also prove $\lambda _\ell (BH_n)\leq 2n(\ell -1)-2\ell +6$ for $4\leq \ell \leq 2n+3$ and the upper bound of $\lambda _\ell (BH_n)$ we obtained is tight for $\ell =4,5$.

Abstract Most graphs have this property: after removing a linear number of vertices from a graph, the surviving graph is either connected or consists of a large connected component and small components containing a small number of vertices. This property can be applied to derive fault-tolerance related network parameters: extra edge connectivity and component edge connectivity. Using this general property, we obtained the $h$-extra edge connectivity and $(h+2)$-component edge connectivity of augmented cubes, Cayley graphs generated by transposition trees, complete cubic networks (including hierarchical cubic networks), generalized exchanged hypercubes (including exchanged hypercubes) and dual-cube-like graphs (including dual cubes).

The h-extra connectivity κh(G) of G is the cardinality of a minimum set S such that G−S is disconnected and each component of G−S has at least h+1 vertices. The conditional diagnosability tc(G) of G is the maximum number t for which G is conditionally t-diagnosable. The relationship between the extra connectivity and the conditional diagnosability under the MM model was discussed in [Theor. Comput. Sci. 618 (2016) 21–29] and [Theor. Comput. Sci. 627 (2016) 36–53]. The open problem that what is the relationship between the conditional diagnosability and the h-extra connectivity under the PMC model for some h was given in [Theor. Comput. Sci. 627 (2016) 36–53]. In this paper, we solve this problem for an n-regular n-connected graph G under certain conditions, and the relation is given by tc(G)=κ3(G)+1 or κ3(G)+2⁠. As applications, we prove that tc(Γn(Δ)) = 8n−27 and κ3(Γn(Δ)) = 8n−28 for the Cayley graph generated by 2-tree Δ and that tc(Qn3) = 8n−11 for the 3-ary n-cubes Qn3⁠.