Edge-disjoint paths in faulty augmented cubes (Q2656959)

Reliability and efficiency are important criteria in the design of interconnection networks and connectivity parameters play a major role in the study of fault-tolerance of networks. The paper under review studies edge-disjoint paths in augmented cubes (\(AQ_n\)) with faulty edges. For a vertex \(v \in V(G)\), the degree of \(v\) in \(G\) is denoted by \(\deg_G(v)\), and \(\delta(G) = \min \{\deg_G(v) \colon v \in V(G)\}\). It is shown that for any faulty edge set \(F \subset E (AQ_n) \) with \(\delta (AQ_n-F) \geq 2\), if \(n \geq 4\) and \(| F| \leq 4n-8\), then for any two vertices \(u,v \in V(AQ_n-F)\), there are \(\min\{\deg_{AQ_n-F} (u), \deg_{AQ_n-F} (v)\}\) edge-disjoint paths connecting \(u\) and \(v\). This result is optimal with respect to the maximum number of faulty edges. Furthermore, the \(g\)-extra edge-connectivity of \(AQ_n\) is determined for \(g=1\) and \(n \geq 2\) and for \(g=2\) and \(n \geq 4\). The \(g\)-extra-connectivity of a graph was introduced by \textit{J. Fàbrega} and \textit{M. A. Fiol} [Discrete Math. 155, No. 1--3, 49--57 (1996; Zbl 0857.05064)].