Abstract
The abstract graph G can model an interconnection network’s topology. A cluster C in G is a node subset of G such that the subgraph induced by C is connected. Theoretically speaking, the order of the maximal component in G from which certain faulty clusters are removed can be referred as an index of fault tolerability. A path consisting of k distinct nodes is abbreviated as \(P_k\). A set F of clusters of G is a \(P_2\)-cut if (i) all clusters of F induce subgraphs that are isomorphic to \(P_2\), and (ii) \(G-F\) is trivial or disconnected. Because of the growing popularity of the hypercube architecture \(Q_n\) in real-world supercomputers, this paper is devoted to exploring the vulnerability of \(Q_n\) based on \(P_2\)-cuts.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Bondy, J.A., Murty, U.S.R.: Graph Theory. Springer, London (2008). https://doi.org/10.1007/978-1-4612-9967-7
Bossard, A., Kaneko, K.: Cluster-fault tolerant routing in a torus. Sensors 20(11), 1–17 (2020)
Fábrega, J., Fiol, M.A.: On the extraconnectivity of graphs. Disc. Math. 155, 49–57 (1996)
Fan, J., Lin, X.: The t/k-diagnosability of the bc graphs. IEEE Trans. Comput. 54(2), 176–184 (2005)
Gu, Q.P., Peng, S.: An efficient algorithm for node-to-node routing in hypercubes with faulty clusters. Comput. J. 39, 14–19 (1996)
Gu, Q.P., Peng, S.: \(k\)-pairwise cluster fault tolerant routing in hypercubes. IEEE Trans. Comput. 46, 1042–1049 (1997)
Gu, Q.P., Peng, S.: Node-to-set and set-to-set cluster fault tolerant routing in hypercubes. Parallel Comput. 24, 1245–1261 (1998)
Harary, F., Hayes, J.P., Wu, H.J.: A survey of the theory of hypercube graphs. Comput. Math. Appl. 15, 277–289 (1988)
Kung, T.L., Lin, C.K.: Cluster connectivity of hypercube-based networks under the super fault-tolerance condition. Disc. Appl. Math. 293, 143–156 (2021)
Saad, Y., Schultz, M.H.: Topological properties of hypercubes. IEEE Tran. Comput. 37, 867–872 (1988)
Sabir, E., Meng, J.: Structure fault tolerance of hypercubes and folded hypercubes. Theor. Comput. Sci. 711, 44–55 (2018)
Yang, W., Meng, J.: Extraconnectivity of hypercubes. Appl. Math. Lett. 22, 887–891 (2009)
Acknowledgements
This work is supported in part by National Science and Technology Council, Taiwan, under Grant No. NSTC 111-2221-E-468-010.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2023 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Teng, YH., Kung, TL. (2023). Vulnerability of the Hypercube Network Based on \(P_2\)-cuts. In: Barolli, L. (eds) Innovative Mobile and Internet Services in Ubiquitous Computing . IMIS 2023. Lecture Notes on Data Engineering and Communications Technologies, vol 177. Springer, Cham. https://doi.org/10.1007/978-3-031-35836-4_24
Download citation
DOI: https://doi.org/10.1007/978-3-031-35836-4_24
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-35835-7
Online ISBN: 978-3-031-35836-4
eBook Packages: Intelligent Technologies and RoboticsIntelligent Technologies and Robotics (R0)