Edge-fault-tolerant strong Menger edge connectivity on regular graphs

Abstract The connectivity of a graph is an important issue in graph theory and is also one of the most important factors in evaluating the reliability and fault tolerance of a network. A graph G is called m-edge-fault-tolerant strongly Menger(m-EFTSM for short) edge connected if there are min ⁡ { deg G − F ⁡ ( x ) , deg G − F ⁡ ( y ) } edge-disjoint paths between any two different vertices x and y in G − F for any F ⊆ E ( G ) with | F | ≤ m . In this paper, we give a necessary and sufficient condition of EFTSM edge connectivity on regular graphs. And we obtain several optimal results about EFTSM edge connectivity on (1, 2)-matching composition networks, each of which is constructed by connecting two graphs via one or two perfect matchings. As applications, we show that the class of n-dimensional hypercube-like networks (included hypercube, crossed cube et al.) are ( n − 2 ) -EFTSM edge connected; show that the n-dimensional folded hypercube is ( n − 1 ) -EFTSM edge connected, and show that the n-dimensional augmented cube is ( 2 n − 3 ) - EFTSM edge connected. The bounds ( n − 2 ) , ( n − 1 ) and ( 2 n − 3 ) are sharp.