The $ g $-extra $ H $-structure connectivity and $ g $-extra $ H $-substructure connectivity of hypercubes

Bo Zhu; Shumin Zhang; Huifen Ge; Chengfu Ye; Bo Zhu; Shumin Zhang; Huifen Ge; Chengfu Ye

doi:10.3934/math.20231267

AIMS Mathematics

2023, Volume 8, Issue 10: 24848-24861. doi: 10.3934/math.20231267

Previous Article Next Article

Research article Special Issues

The $ g $-extra $ H $-structure connectivity and $ g $-extra $ H $-substructure connectivity of hypercubes

1.
Department of Computer, Qinghai Normal University, Xining, Qinghai 810008, China
2.
School of Mathematics and Statistics, Qinghai Normal University, Xining, Qinghai 810008, China
3.
Academy of Plateau Science and Sustainability, People's Government of Qinghai Province and Beijing Normal University, China

Received: 24 June 2023 Revised: 01 August 2023 Accepted: 09 August 2023 Published: 24 August 2023
MSC : 05C40, 05C07

At present, the reliability of interconnection networks of multiprocessing systems has become a hot topic of research concern for parallel computer systems. Conditional connectivity is an important parameter to measure the reliability of an interconnected network. In reality, the failure of one node will inevitably have a negative impact on the surrounding nodes. Often it is the specific structures that fail in an interconnected network. Therefore, we propose two novel kinds of connectivity, called $ g $-extra $ H $-structure connectivity and $ g $-extra $ H $-substructure connectivity, to go for a more accurate measure of the reliability of the network. Hypercube network is the most dominant interconnection network topology used by computer systems today, for example, the famous parallel computing systems Cray $ T3D $, Cray $ T3E $, $ IBM $ Blue Gene, etc. are built with it as the interconnection network topology. In this paper, we obtain the results of the $ g $-extra $ H $-structure connectivity and the $ g $-extra $ H $-substructure connectivity of the hypercubes when the specific structure is $ P_k $ and $ g = 1 $.
- conditional connectivity,
- $ g $-extra $ H $-structure connectivity,
- $ g $-extra $ H $-substructure connectivity,
- hypercube
Citation: Bo Zhu, Shumin Zhang, Huifen Ge, Chengfu Ye. The $ g $-extra $ H $-structure connectivity and $ g $-extra $ H $-substructure connectivity of hypercubes[J]. AIMS Mathematics, 2023, 8(10): 24848-24861. doi: 10.3934/math.20231267

Related Papers:

Abstract

At present, the reliability of interconnection networks of multiprocessing systems has become a hot topic of research concern for parallel computer systems. Conditional connectivity is an important parameter to measure the reliability of an interconnected network. In reality, the failure of one node will inevitably have a negative impact on the surrounding nodes. Often it is the specific structures that fail in an interconnected network. Therefore, we propose two novel kinds of connectivity, called $ g $-extra $ H $-structure connectivity and $ g $-extra $ H $-substructure connectivity, to go for a more accurate measure of the reliability of the network. Hypercube network is the most dominant interconnection network topology used by computer systems today, for example, the famous parallel computing systems Cray $ T3D $, Cray $ T3E $, $ IBM $ Blue Gene, etc. are built with it as the interconnection network topology. In this paper, we obtain the results of the $ g $-extra $ H $-structure connectivity and the $ g $-extra $ H $-substructure connectivity of the hypercubes when the specific structure is $ P_k $ and $ g = 1 $.

References

[1]	J. A. Bondy, U. S. R. Murty, Graph theory, New York: Springer, 2008.
[2]	S. Eminjan, J. Meng, Structure fault tolerance of hypercubes and folded hypercubes, Theor. Comput. Sci., 711 (2018), 44–55. https://doi.org/10.1016/j.tcs.2017.10.032 doi: 10.1016/j.tcs.2017.10.032
[3]	J. Fàbrega, M. A. Fiol, Extraconnectivity of graphs with large girth, Discrete Math., 127 (1994), 163–170. https://doi.org/10.1016/0012-365X(92)00475-7 doi: 10.1016/0012-365X(92)00475-7
[4]	J. Fàbrega, M. A. Fiol, On the extraconnectivity of graphs, Discrete Math., 155 (1996), 49–57. https://doi.org/10.1016/0012-365X(94)00369-T doi: 10.1016/0012-365X(94)00369-T
[5]	J. Guo, M. Lu, The extra connectivity of bubble-sort star graphs, Theor. Comput. Sci., 645 (2016), 91–99. https://doi.org/10.1016/j.tcs.2016.06.043 doi: 10.1016/j.tcs.2016.06.043
[6]	C. Li, S. Lin, S. Li, Structure connectivity and substructure connectivity of star graphs, Discrete Appl. Math., 284 (2020), 472–480. https://doi.org/10.1016/j.dam.2020.04.009 doi: 10.1016/j.dam.2020.04.009
[7]	D. Li, X. Hu, H. Liu, Structure connectivity and substructure connectivity of twisted hypercubes, Theor. Comput. Sci., 796 (2019), 169–179. https://doi.org/10.1016/j.tcs.2019.09.007 doi: 10.1016/j.tcs.2019.09.007
[8]	H. Lv, T. Wu, Structure and substructure connectivity of Balanced Hypercubes, Bull. Malays. Math. Sci. Soc., 43 (2020), 2659–2672. https://doi.org/10.1007/s40840-019-00827-4 doi: 10.1007/s40840-019-00827-4
[9]	C. Li, S. Lin, S. Li, Structure connectivity and substructure connectivity of $(n, k)$-star graph networks, 2018 15th International Symposium on Pervasive Systems, Algorithms and Networks (Ⅰ-SPAN), 2018,240–246. https://doi.org/10.1109/I-SPAN.2018.00046 doi: 10.1109/I-SPAN.2018.00046
[10]	C. K. Lin, L. Zhang, J. Fan, D. Wang, Structure connectivity and substructure connectivity of hypercubes, Theor. Comput. Sci., 634 (2016), 97–107. https://doi.org/10.1016/j.tcs.2016.04.014 doi: 10.1016/j.tcs.2016.04.014
[11]	L. Lin, L. Xu, S. Zhou, Conditional diagnosability and strong diagnosability of split-star networks under the PMC model, Theor. Comput. Sci., 562 (2015), 565–580. https://doi.org/10.1016/j.tcs.2014.10.046 doi: 10.1016/j.tcs.2014.10.046
[12]	W. Han, S. Wang, The $g$-extra conditional diagnosability of folded hypercubes, Appl. Math. Sci., 9 (2015), 7247–7254. http://dx.doi.org/10.12988/ams.2015.510679 doi: 10.12988/ams.2015.510679
[13]	F. Harary, Conditional connectivity, Networks, 13 (1983), 347–357. https://doi.org/10.1002/net.3230130303 doi: 10.1002/net.3230130303
[14]	E. Sabir, J. Meng, Structure fault tolerance of hypercubes and folded hypercubes, Theoret. Comput. Sci., 711 (2018), 44–55. https://doi.org/10.1016/j.tcs.2017.10.032 doi: 10.1016/j.tcs.2017.10.032
[15]	J. Xu, Q. Zhu, X. Hou, T. Zhou, On restricted connectivity and extra connectivity of hypercubes and folded hypercubes, J. Shanghai Jiaotong Unvi., 10 (2005), 203–207.
[16]	W. Yang, J. Meng, Extraconnectivity of hypercubes, Appl. Math. Lett., 22 (2009), 887–891. https://doi.org/10.1016/j.aml.2008.07.016 doi: 10.1016/j.aml.2008.07.016
[17]	G. Zhang, D. Wang, Structure connectivity and substructure connectivity of bubble-sort star graph networks, Appl. Math. Comput., 363 (2019), 124632. https://doi.org/10.1016/j.amc.2019.124632 doi: 10.1016/j.amc.2019.124632
[18]	G. Zhang, D. Wang, The structure fault tolerance of arrangement graphs, Appl. Math. Comput., 400 (2021), 126039. https://doi.org/10.1016/j.amc.2021.126039 doi: 10.1016/j.amc.2021.126039
[19]	M. M. Zhang, J. X. Zhou, On $g$-extra connectivity of folded hypercubes, Theoret. Comput. Sci., 593 (2015), 146–153. https://doi.org/10.1016/j.tcs.2015.06.008 doi: 10.1016/j.tcs.2015.06.008
[20]	Q. Zhu, X. K. Wang, G. Cheng, Reliability evaluation of BC networks, IEEE Trans. Comput., 62 (2013), 2337–2340. https://doi.org/10.1109/TC.2012.106 doi: 10.1109/TC.2012.106
[21]	Q. Zhu, X. Zhang, The $h$-extra conditional diagnosability of hypercubes under the $PMC$ model and $MM^$ model, Int. J. Comput. Math.: Comput. Syst. Theory*, 1 (2016) 141–150. https://doi.org/10.1080/23799927.2017.1289247 doi: 10.1080/23799927.2017.1289247

Reader Comments

Your name:*

Email:*
© 2023 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)