Edge-disjoint paths in faulty augmented cubes

Motivated by evaluating the reliability and fault tolerance of a network, we consider edge-disjoint paths in augmented cubes with faulty edges. We show that for any faulty edge set F subset of E(AQ(n)) and delta (AQ(n) - F) >= 2, if vertical bar F vertical bar <= 4n - 8 for n >= 4, there are min{deg(AQn - F)(u), deg(AQn - F)(nu)} edge-disjoint paths connected any two vertices u and nu in AQ(n) - F, where deg(AQn - F)(u) and deg(AQn - F)(nu) are the degree of vertices u and nu in AQ(n) - F, respectively. This result is optimal with respect to the maximum number of faulty edges. Simultaneously, we determine lambda(1)(AQ(n)) for n >= 2, and lambda(2)(AQ(n)) for n >= 4, where lambda(g)(AQ(n)) is the g-extra edge-connectivity of AQ(n). Given a graph G and a non-negative integer g, the g-extra edge-connectivity of G, denoted lambda(g)(G), is the minimum cardinality of a set of edges in G, if it exists, whose deletion disconnects G and leaves each remaining component with more than g vertices. (C) 2021 Elsevier B.V. All rights reserved.

Automated summary

This article investigates edge-disjoint paths in augmented cubes with faulty edges, proving some important results and introducing the concept of extra edge-connectivity.