Abstract | ||
---|---|---|
Let G=(V,E) be a connected graph. The h-restricted edge connectivity λh(G) of G is defined as the minimum size |F| of a set F of edges such that G−F is disconnected and every component of G−F contains at least h vertices. G is said to be λh-connected if λh(G) exists. Let ξh(G)=min{|ω(A)|:G[A]is connected and|A|=h}, where ω(A) is the subset of edges having exactly one end node in A and G[A] is the subgraph induced by the node set A. A λh-connected graph G is said to be λh-optimal if λh(G)=ξh(G). A λh-optimal graph G is said to be m-λh-optimal if G−F is still λh-optimal for any edge subset F⊆E(G) with |F|≤m. The edge fault tolerance of a λh-optimal graph G with respect to the λh-optimal property, denoted by ρh(G), is the maximum integer m such that G is m-λh-optimal. In this paper, we give the lower and upper bounds of ρ2 for λ2-optimal graphs. As applications, we determine exact values of ρ2 for two families of networks. |
Year | DOI | Venue |
---|---|---|
2019 | 10.1016/j.tcs.2019.03.024 | Theoretical Computer Science |
Keywords | DocType | Volume |
Fault tolerance,Restricted edge connectivity,λh-optimal,Networks,Graphs | Journal | 783 |
ISSN | Citations | PageRank |
0304-3975 | 1 | 0.39 |
References | Authors | |
0 | 3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Yaoyao Zhang | 1 | 1 | 0.39 |
Shuang Zhao | 2 | 30 | 12.77 |
Jixiang Meng | 3 | 353 | 55.62 |