The generalized 4-connectivity of balanced hypercubes

Cheng, Dongqin 

Discussiones Mathematicae. Graph Theory, Tome 44 (2024) no. 3, pp. 1079-1106

Résumé

The balanced hypercube is a kind of highly symmetrical network and possesses many good properties. Generalized connectivity is a new measurement of interconnection networks' fault tolerance. The internally disjoint N-trees are edge-disjoint trees but with intersecting vertex set N. Let κ(N) be the maximum number of internally disjoint N-trees and the generalized k-connectivity of G be κ_k(G)=min{κ(N) | N ⊂ V(G) and | N | =k}. In this paper, we study the n-dimensional balanced hypercube BH_n and demonstrate that κ_4(BH_n)=2n-1 for n ≥ 1.

Détail

Keywords: interconnection network, balanced hypercube, generalized connectivity, fault tolerance

Bibliographie

[1] J.A. Bondy and U.S.R. Murty, Graph Theory, in: Grad. Texts in Math. 244 (Springer, New York, 2008).

[2] G. Chartrand, S.F. Kapoor, L. Lesniak and D.R. Lick, Generalized connectivity in graphs, Bull. Bombay Math. Colloq. 2 (1984) 1–6.

[3] D. Cheng, R.-X. Hao and Y.-Q. Feng, Two node-disjoint paths in balanced hypercubes, Appl. Math. Comput. 242 (2014) 127–142. https://doi.org/10.1016/j.amc.2014.05.037

[4] D. Cheng, The h-restricted connectivity of balanced hypercubes, Discrete Appl. Math. 305 (2021) 133–141. https://doi.org/10.1016/j.dam.2021.08.036

[5] D. Du and X. Hu, Steiner Tree Problem in Computer Communication Networks (World Scientific, Singapore, 2008). https://doi.org/10.1142/6729

[6] S. Li, X. Li and W. Zhou, Sharp bounds for the generalized connectivity \kappa3(G), Discrete Math. 310 (2010) 2147–2163. https://doi.org/10.1016/j.disc.2010.04.011

[7] S. Li, Some Topics on Generalized Connectivity of Graphs, Ph.D. Thesis (Nankai University, 2012).

[8] L. Li, X. Zhang, Q. Zhu and Y. Bai, The 3-extra conditional diagnosability of balanced hypercubes under MM* model, Discrete Appl. Math. 309 (2022) 310–316. https://doi.org/10.1016/j.dam.2021.04.004

[9] C. Li, S. Lin and S. Li, The 4-set tree connectivity of (n, k)-star networks, Theoret. Comput. Sci. 844 (2020) 81–86. https://doi.org/10.1016/j.tcs.2020.08.004

[10] S. Lin and Q. Zhang, The generalized 4-connectivity of hypercubes, Discrete Appl. Math. 220 (2017) 60–67. https://doi.org/10.1016/j.dam.2016.12.003

[11] H. Liu and D. Cheng, The generalized 3-connectivity and 4-connectivity of crossed cube, Discuss. Math. Graph Theory(2022), in press. https://doi.org/10.7151/dmgt.2474

[12] H. Liu and D. Cheng, The generalized 4-connectivity of folded hypercube, Int. J. Comput. Math. Comput. Syst. Theory 7(4) (2022) 235–245. https://doi.org/10.1080/23799927.2022.2123405

[13] H. Liu and D. Cheng, Structure fault tolerance of balanced hypercubes, Theoret. Comput. Sci. 845 (2020) 198–207. https://doi.org/10.1016/j.tcs.2020.09.015

[14] H. Lü and H. Zhang, Hyper-Hamiltonian laceability of balanced hypercubes, J. Supercomput. 68 (2014) 302–314. https://doi.org/10.1007/s11227-013-1040-6

[15] H. Lü and T. Wu, Edge-disjoint Hamiltonian cycles of balanced hypercubes, Inform. Process. Lett. 144 (2019) 25–30. https://doi.org/10.1016/j.ipl.2018.12.004

[16] Y. Saad and M.H. Schultz, Topological properties of hypercubes, IEEE Trans. Comput. 37 (1988) 867–872. https://doi.org/10.1109/12.2234

[17] C. Wei, R.-X. Hao and J.-M. Chang, The reliability analysis based on the generalized connectivity in balanced hypercubes, Discrete Appl. Math. 292 (2021) 19–32. https://doi.org/10.1016/j.dam.2020.12.011

[18] C. Wei, R.-X. Hao and J.-M. Chang, Two-disjoint-cycle-cover bipancyclicity of balanced hypercubes, Appl. Math. Comput. 381 (2020) 125305. https://doi.org/10.1016/j.amc.2020.125305

[19] J. Wu and K. Huang, The balanced hypercube: a cube-based system for fault-tolerant applications, IEEE Trans. Comput. 46 (1997) 484–490. https://doi.org/10.1109/12.588063

[20] M. Xu, X.-D. Hu and J.-M. Xu, Edge-pancyclicity and Hamiltonian laceability of the balanced hypercubes, Appl. Math. Comput. 189 (2007) 1393–1401. https://doi.org/10.1016/j.amc.2006.12.036

[21] M. Xu and Y. Wei, The h-edge tolerable diagnosability of balanced hypercubes, Theoret. Comput. Sci. 795 (2019) 540–546. https://doi.org/10.1016/j.tcs.2019.08.007

[22] M.-C. Yang, Conditional diagnosability of balanced hypercubes under the PMC model, Inform. Sci. 222 (2013) 754–760. https://doi.org/10.1016/j.ins.2012.08.014

[23] Y. Yang and L. Zhang, Fault-tolerant-prescribed hamiltonian laceability of balanced hypercubes, Inform. Process. Lett. 145 (2019) 11–15. https://doi.org/10.1016/j.ipl.2019.01.002

[24] S.-L. Zhao and R.-X. Hao, The generalized 4-connectivity of exchanged hypercubes, Appl. Math. Comput. 347 (2019) 342–353. https://doi.org/10.1016/j.amc.2018.11.023

[25] S.-L. Zhao, R.-X. Hao and J. Wu, The generalized 4-connectivity of hierarchical cubic networks, Discrete Appl. Math. 289 (2021) 194–206. https://doi.org/10.1016/j.dam.2020.09.026

[26] S-L. Zhao and J.-M. Chang, Reliability assessment of the divide-and-swap cube in terms of generalized connectivity, Theoret. Comput. Sci. 943 (2023) 1–15. https://doi.org/10.1016/j.tcs.2022.12.005

[27] S.-L. Zhao, J.-M. Chang and H.-Z. Li, The generalized 4-connectivity of pancake graphs, Discrete Appl. Math. 327 (2023) 77–86. https://doi.org/10.1016/j.dam.2022.11.020

[28] J.-X. Zhou, Z.-L. Wu, S.-C. Yang and K.-W. Yuan, Symmetric property and reliability of balanced hypercube, IEEE Trans. Comput. 64 (2015) 876–881. https://doi.org/10.1109/TC.2014.2304391