Journal
THEORETICAL COMPUTER SCIENCE
Volume 847, Issue -, Pages 39-48Publisher
ELSEVIER
DOI: 10.1016/j.tcs.2020.09.035
Keywords
Fault-tolerance; Maximal local edge connectivity; Strong Menger edge connectivity; Regular graphs; (1,2)-Matching composition networks
Categories
Funding
- National Natural Science Foundation of China [11571044, 61373021]
- Fundamental Research Funds for the Central University of China
- Project of Scientific Research Fund of Hunan Provincial Science and Technology Department [2018WK4006]
- General Project of Hunan Provincial Education Department of China [19C1742]
Ask authors/readers for more resources
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 subset of E(G) with vertical bar F vertical bar <= 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 (2n - 3) EFTSM edge connected. The bounds (n - 2), (n - 1) and (2n - 3) are sharp. (C) 2020 Elsevier B.V. All rights reserved.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available