Fault tolerance of augmented cubes (Q2443412): Difference between revisions

A subset of vertices \(S\) of a graph \(G\) is called an \(h\)-vertex-cut if the removal of \(S\) disconnects \(G\) and every component of \(G-S\) has more than \(h\) vertices. The \(h\)-extra connectivity \(\kappa_h(G)\) is defined as the minimum cardinality of an \(h\)-vertex-cut of \(G\). One can define similar notions replacing vertices by edges and obtains the \(h\)-edge-cut and \(h\)-extra edge-connectivity, respectively. In this paper, the authors determine the 2-extra connectivity and the 2-extra edge-connectivity of the \(n\)-dimensional augmented cube \(AQ_n\). The \(n\)-dimensional augmented cube \(AQ_n\) was introduced by \textit{S. A. Choudum} and \textit{V. Sunitha} [Networks 40, No. 2, 71--84 (2002; Zbl 1019.05052)] and is defined recursively as follows. The graph \(AQ_1\) is the complete graph \(K_2\) with vertex set \(\{0,1\}\). For \(n\geq 2\), the graph \(AQ_n\) is obtained from two disjoint isomorphic copies of \(AQ_{n-1}\), denoted \(AQ^{0}_{n-1}\) and \(AQ^{1}_{n-1}\), with \(V(AQ^{0}_{n-1})=\{0x_{n-1}\dots x_1: x_i\in \{0,1\}, 1\leq i\leq n-1\}\) and \(V(AQ^{1}_{n-1})=\{1y_{n-1}\dots y_1: y_i\in \{0,1\}, 1\leq i\leq n-1\}\) having \(0x_{n-1}\dots x_1\in V(AQ^{0}_{n-1})\) adjacent to \(1y_{n-1}\dots y_1\in V(AQ^{1}_{n-1})\) if and only if either \(x_i=y_i\) for \(1\leq i\leq n-1\) or \(x_i=1-y_i\) for \(1\leq i\leq n-1\).