Cited By
View all- Huang ZYang YZhang MYang X(2025)Assessing reliability in Complete Josephus Cube networks via strongly Menger edge-connectivityThe Journal of Supercomputing10.1007/s11227-024-06564-181:1Online publication date: 1-Jan-2025
Strongly Menger-edge-connectedness and strongly Menger-vertex-connectedness of regular networks
Pages 50 - 67
Abstract
Let F be a conditional faulty edge set of a graph G. Here the condition imposed on F is (GF)r for some fixed integer r. The graph G is called F-strongly Menger-edge-connected of order r if each pair of distinct vertices u and v are connected by min{degGF(u), degGF(v)} edge-disjoint paths in GF, where degGF(u) and degGF(v) are the degrees of u and v in GF, respectively. A graph G is t-strongly Menger-edge-connected of order r if G is F-strongly Menger-edge-connected of order r for every FE(G) with |F|t. One can consider the vertex version in an analogous way.There are a number of papers with results for r=2 for several popular classes of interconnection network. In this paper, we develop a unified approach by considering various sufficient conditions of a regular graph to be F-strongly Menger-edge-connected of order r and the corresponding vertex version. As corollaries, several results on fundamental classes of interconnection networks are presented including new results as well as strengthening of existing results such as the one given by Qiao and Yang (2017) [20]. The concepts of F-strongly Menger-edge-connected of order 2 is generalized to that of F-strongly Menger-edge-connected of order r and the corresponding vertex version.We provide a number of sufficient conditions for a k-regular graph to be F-strongly Menger-edge-connected (Menger-vertex-connected) of order r.We get the several new results for regular graphs such as:If G is triangle-free and super (t+k1)-edge-connected of order r+1, then G is t-strongly Menger-edge-connected of order r.If t2k6 and G is super (t+k1)-edge-connected of order r+1, then G is t-strongly Menger-edge-connected of order r.
References
[1]
S. Abraham, K. Padmanabhan, The twisted cube topology for multiprocessors: a study in network asymmetry, J. Parallel Distrib. Comput., 13 (1991) 104-110.
[2]
J.R. Armstrong, F.G. Gray, Fault diagnosis in a Boolean n-cube array of microprocessors, IEEE Trans. Comput., C-30 (1981) 587-590.
[3]
D. Cheng, R.-X. Hao, Various cycles embedding in faulty balanced hypercubes, Inform. Sci., 297 (2015) 140-153.
[4]
D. Cheng, R.-X. Hao, Y.-Q. Feng, Vertex-fault-tolerant cycles embedding in balanced hypercubes, Inform. Sci., 288 (2014) 449-461.
[5]
E. Cheng, R.-X. Hao, S. He, A study of Menger vertex and edge connectedness, Oakland University Technical Report Series 2017-1.
[6]
E. Cheng, L. Lipman, L. Liptk, Matching preclusion and conditional matching preclusion for regular interconnection networks, Discrete Appl. Math., 160 (2012) 1936-1954.
[7]
E. Cheng, K. Qiu, Z. Shen, A strong connectivity property of the generalized exchanged hypercube, Discrete Appl. Math., 216 (2017) 529-539.
[8]
E. Cheng, K. Qiu, Z. Shen, On the conditional diagnosability of matching composition networks, Theoret. Comput. Sci., 557 (2014) 101-114.
[9]
K. Efe, The crossed cube architecture for parallel computing, IEEE Trans. Parallel Distrib. Syst., 3 (1992) 513-524.
[10]
A.H. Esfahanian, L.M. Ni, B.E. Sagan, The twisted n-cube with application to multiprocessing, IEEE Trans. Comput., 40 (1991) 88-93.
[11]
J.X. Fan, L.Q. He, BC interconnection networks and their properties, Chinese J. Comput., 26 (2003) 84-90.
[12]
M.-M. Gu, R.-X. Hao, Y.-Q. Feng, Fault-tolerant cycle embedding in balanced hypercubes with faulty vertices and faulty edges, J. Interconnect. Netw., 15 (2015).
[13]
W-S. Hong, S-Y. Hsieh, Extra edge connectivity of hypercube-like networks, Int. J. Parallel Emergent Distrib. Syst., 28 (2013) 123-133.
[14]
S-Y. Hsieh, Y.-H. Chang, Extra connectivity of k-ary n-cube networks, Theoret. Comput. Sci., 443 (2012) 63-69.
[15]
H. L, On extra connectivity and extra edge-connectivity of balanced hypercubes, Int. J. Comput. Math., 94 (2017) 813-820.
[16]
H. L, X. Li, H. Zhang, Matching preclusion for balanced hypercubes, Theoret. Comput. Sci., 465 (2012) 10-20.
[17]
E. Oh, J. Chen, On strong Menger-connectivity of star graphs, Discrete Appl. Math., 129 (2003) 499-511.
[18]
E. Oh, On Strong Fault Tolerance (or Strong Menger-Connectivity) of Multicomputer Networks, Computer Science A&M University, August 2004.
[19]
E. Oh, J. Chen, Strong fault-tolerance: parallel routing in star networks with faults, J. Interconnect. Netw., 4 (2003) 113-126.
[20]
Y.L. Qiao, W.H. Yang, Edge disjoint paths in hypercubes and folded hypercubes with conditional faults, Appl. Math. Comput., 294 (2017) 96-101.
[21]
L. Shih, C. Chiang, L. Hsu, J. Tan, Strong Menger connectivity with conditional faults on the class of hypercube-like networks, Inform. Process. Lett., 106 (2008) 64-69.
[22]
J. Wu, K. Huang, The balanced hypercubes: a cube-based system for fault-tolerant applications, IEEE Trans. Comput., 46 (1997) 484-490.
[23]
J.M. Xu, M. Xu, Q. Zhu, The super connectivity of shuffle-cubes, Inform. Process. Lett., 96 (2005) 123-127.
[24]
J.M. Xu, Combination of Network Theory, Science Press, Beijing, 2013.
[25]
M-C. Yang, Super connectivity of balanced hypercubes, Appl. Math. Comput., 219 (2012) 970-975.
[26]
W.H. Yang, H. Li, On reliability of the folded hypercubes in terms of the extra edge-connectivity, Inform. Sci., 272 (2014) 238-243.
[27]
W.H. Yang, S. Zhao, S. Zhang, Strong Menger connectivity with conditional faults of folded hypercubes, Inform. Process. Lett., 125 (2017) 30-34.
[28]
X. Yang, D.J. Evans, G.M. Megson, On the maximal connected component of hypercube with faulty vertices III, Int. J. Comput. Math., 83 (2006) 27-37.
- Strongly Menger-edge-connectedness and strongly Menger-vertex-connectedness of regular networks
Recommendations
Adjacent vertex-distinguishing edge and total chromatic numbers of hypercubes
An adjacent vertex-distinguishing edge coloring of a simple graph G is a proper edge coloring of G such that incident edge sets of any two adjacent vertices are assigned different sets of colors. A total coloring of a graph G is a coloring of both the ...
The Cyclic Edge-Connectivity of Strongly Regular Graphs
Let G be a connected graph. An edge cut set M of G is a cyclic edge cut set if there are at least two components of $$G-M$$G-M which contain a cycle. The cyclic edge-connectivity of G is the minimum cardinality of a cyclic edge cut set (if exists) of G. ...
Assessing reliability in Complete Josephus Cube networks via strongly Menger edge-connectivity
AbstractThe fault tolerance of an interconnection network relies on its topological parameters of a graph G, with strongly Menger edge-connectivity being a crucial factor. A connected graph G is denoted as strongly Menger edge-connected, if for any two ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Copyright © Elsevier B.V.
Publisher
Elsevier Science Publishers Ltd.
United Kingdom
Publication History
Published: 30 June 2018
Author Tags
Qualifiers
- Research-article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- View Citations1Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 07 Mar 2025
Other Metrics
Citations
Cited By
View all- Huang ZYang YZhang MYang X(2025)Assessing reliability in Complete Josephus Cube networks via strongly Menger edge-connectivityThe Journal of Supercomputing10.1007/s11227-024-06564-181:1Online publication date: 1-Jan-2025